Attacks on Online Learners: a Teacher-Student Analysis
Authors: Riccardo Giuseppe Margiotta
Sebastian Goldt
Guido Sanguinetti
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial attacks
data poisoning
online learning
optimal control
teacher-student setup
solvable model
TL;DR: We analyze online label attacks, characterizing analytically the victim's behavior in a teacher-student setup, and demonstrating empirically that greedy attacks can be very effective.

Abstract: Machine learning models are famously vulnerable to adversarial attacks: small ad-hoc perturbations of the data that can catastrophically alter the model predictions. While a large literature has studied the case of test-time attacks on pre-trained models, the important case of attacks in an online learning setting has received little attention so far. In this work, we use a control-theoretical perspective to study the scenario where an attacker may perturb data labels to manipulate the learning dynamics of an online learner. We perform a theoretical analysis of the problem in a teacher-student setup, considering different attack strategies, and obtaining analytical results for the steady state of simple linear learners. These results enable us to prove that a discontinuous transition in the learner's accuracy occurs when the attack strength exceeds a critical threshold. We then study empirically attacks on learners with complex architectures using real data, confirming the insights of our theoretical analysis. Our findings show that greedy attacks can be extremely efficient, especially when data stream in small batches.

Attacks on Online Learners: a Teacher-Student Analysis
Riccardo G. Margiotta'
Sebastian Goldt
Guido Sanguinetti
International School for Advanced Studies, Trieste, Italy
Abstract
Machine learning models are famously vulnerable to adversarial attacks: small ad- hoc perturbations of the data that can catastrophically alter the model predictions. While large literature has studied the case of test-time attacks pre-trained models, the important case of attacks in an online learning setting has received little attention so far. In this work, we control-theoretical perspective to study the scenario where an attacker may perturb data labels to manipulate the learning dynamics of online learner: We perform theoretical analysis of the problem in a teacher-student setup, considering different attack strategies, and obtaining analytical results for the steady state of simple linear learners. These results enable us to prove that a discontinuous transition in the learner's ' accuracy occurs when the attack strength exceeds a critical threshold. We then study empirically attacks on learners with complex architectures using real data, confirming the insights of our theoretical analysis. Our findings show that greedy attacks can extremely efficient, especially when data stream in small batches.
Introduction
Adversarial attacks pose remarkable threat to modern machine learning (ML), models based on deep networks have proven highly vulnerable to such attacks. Understanding adversarial attacks is therefore of paramount importance, and much work has been done in this direction; see [1, 2] for reviews. The standard setup of adversarial attacks aims to change the predictions of a trained model by applying minimal perturbation to its inputs. In the data poisoning scenario, instead, inputs and/or outputs of the training data are corrupted by an attacker whose goal is to force the learner to get as close as possible to "nefarious" target model, for example include a backdoor [3, 4]. Data poisoning has also received considerable attention that has focused on the offline setting, where models are trained on fixed datasets [5]. An increasing number of real-world applications instead require that machine learning models are continuously updated using streams of data, often relying on transfer-learning techniques. In many cases, the streaming data can be subject adversarial manipulations. Examples include learning from user-genesn generaeed data (GPT-based models) and collecting information from the environment, as e-commerce applications. Federated learning constitutes yet another important example where machine learning models are updated over time, and where malicious nodes in the federation have private access to a subset of the data used for training.
In the online setting, the attacker intercepts the data stream and modifies it to move the learner towards the nefarious target model, Fig. 1-A for schematic where attacks change the labels. In this streaming scenario, the attacker needs to predict both the future data stream and model states, accounting for the effect of its own perturbations, so as decide how to poison the current data batch. Finding the best possible attack policy for given data batch and learner state can be formalized as stochastic optimal control problem, with opposing costs given by the magnitude of perturbations
R. G. Margiotta (rimargiesissa. it) is the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and the distance between learner and attacker's 's target [6]. The ensuing dynamics have surprising features. Take for example Fig. 1-B, where we show the aceuracy of an attacked model (a logistic regression classifier classifying MNIST images) as a function of the attack strength (we define this quantity in Sec. 2.2). Even in such a simple model, we observe strong nonlinear behavior where the accuracy drops dramatically when crossing critical attack strength. This observation raises several questions about the vulnerability of learning algorithms to online data poisoning. What is the effect of the perturbations on the learning dynamics and long-term behavior of the model under attack? Is there a minimum perturbation strength required for the attacker to achieve a predetermined goal? And how do different attack strategies compare in terms of efficacy? We investigate these questions by analyzing the attacker's 's control problem from a theoretical standpoint in the teacher-student setup, popular framework for studying machine learning models in a controlled way [7-10]. We obtain analytical results characterizing the steady state of the attacked model in a linear regression setting, and we show that a simple greedy attack strategy can perform empirically replicated across more complex learners in the teacher-student setup, and the fundamental aspects of our theoretical results are also reflected in real-data experiments.
optimally. This observation is
Main contributions
We present a theoretical analysis of online data poisoning in the teacher-student setup, providing analytical results for the linear regression case [RESULT 1-5], In particular, we demonstrate that a phase transition takes place when the batch size approaches infinity, signaled by a discontinuity in the accuracy of the student against the attacker's 's strength [RESULT 2].
We provide a quantitative comparison between different attack strategies. Surprisingly, we find that properly calibrated greedy attacks can be as effective as attacks with full knowledge of the incoming data stream. Greedy attacks are also computationally efficient, thus constituting a remarkable threat to online learners.
We empirically study online data poisoning real datasets (MNIST, CIFARIO), using archi- tectures of varying complexities including LeNet, ResNet, and VGG. We observe qualitative features that are consistent with our theoretical predictions, providing validation for our findings.
1.1 Further related work
Data poisoning attacks have been the subject of wide range of studies. Most of this research focused on the offline (or batch) setting, where the attacker interacts with the data only once before training starts [3, 11-1 Mei et al. notably proposed optimization approach for offline data poisoning [15]. Wang and Chaudhuri addressed a streaming-datt setting, but in the idealized scenario where the attacker has access to the full (future) data stream (the so-called clairvoyant setting), which effectively reduces the online problem to an offline optimization [16]. So far, the case of online data poisoning has received only a few contributions with a genuine online perspective. In [17], Pang and coauthors investigated attacks on online learners with poisoned batches that aim for an immediate disruptive impact rather than manipulating the long-tern learning dynamics. Zhang et al. proposed an optimal control formulation of online data poisoning by following a parallel line of research, that of online teaching [18, 19], focussing then on practical attack strategies that perturb the input [6]. Our optimal control perspective is similar to that of Zhang and co-authors, though our contribution differs from theirs in various aspects. First, we consider a supervised learning setting where attacks involve data labels, and not input data. We note that attacks on the labels have a reduced computational cost compared to high- dimensional adversarial perturbations of the inputs, which makes label poisoning more convenient in streaming scenario. Second, we provide a theoretical analysis and explicit results for the dynamics of the attacked models, and we consider non-linear predictors in experiments. We observe that our setup is reminiscent of continual learning, which has also recently been analyzed in a teacher-studens setup [20]. However, in online data poisoning the labels are dynamically changed by the attacker drive the learner towards desired target. In continual learning there is no entity that actively modifies the labels, and the learner simply switches from one task to another. Finally, we note that standard (static, test-time) adversarial attacks have been studied in teacher-student framework [21].
Reproducibility. The code and details for implementing our experiments are available here.
2

---

A.
B.
C.
Sp 3
Altacker target: y*
1.0
1.0
allacks
accuracy
attacck stree Strength
Teacher input: label y
0
L
0.5
3 0.5
Student
0.0
0.0
A/
01
0.1
10
100
3000
6000
attack strength
SGD atep
Figure 1: Problem setup and key experimental observations. A: The environment (teacher) generates sequence of clean data with 11th input Iμ and label v/.- The attacker perturbs the labels towards nefarious target 5/z = x² (Ix). At each training step, the predictions Vfz of the learner (student) and the perturbed labels vf. are used compute the loss and update the learner parameters. B: accuracy vs attack strength of a logistic regression classifying MNIST digits and 7 under online tabel-flipping attacks. C: relative distance dy of the logistic learner SGD step μ during the clean training phase, and for training under attacks of increasing attack strength.
Problem setup
2.1 The teacher, the student, and the attacker
The problem setup is depicted in Fig. 1-A. There are three entities: the teacher, the student, and the attacker. The teacher is model of the environment, which generates stream of clean input- output data batches. The inputs x E RD have elements sampled from a distribution Pa. while clean labels are provided by the scalar teacher function: y' 8' (x)). The 1²th batch of the stream BPP = [(T p) with the batch size. The altacker intercepts the clean batch p and perturbs the labels as to make the student learn the target function o². The student d², represents the learning model, and updates its weights 8% on the stream of perturbed batches via SGD, using each (perturbed) batch only once. We will consider teacher, attacker's 's target, and student with the same architecture p(x; 0); they only differ by the value of their parameters, respectively #5, 0", H5. We will refer to this Saaeber-Stdent-Atttt
setup the TSA problem.
If the student trained directly on the input-label pairs provided by the teacher, we would recover the standard teacher-student setup that has been analyzed extensively in the literature [7-10]. The key novelty of this paper that we consider a setup where each new batch of data is instead poisoned by the attacker with the attempt of deviating the student towards different target function.
2.2
The attack
The goal of the attacker for the student to predict target label V² = (xx) for each given input x. Target label and clean label can coincide for specific inputs, however they won't generally do so. The attacker performs an action O₂ that produces perturbed labels as
5 = (1(1app) ap) + yyy aps yaa
a₂ [amin Amax)
(I)
Note that an implies no perturbation, while for a₂ perturbed and target labels coincide. We allow amin < O and 6max > 1 to model attackers that underfovershoot. The attacker's action thus constitutes the control variable of the TSA problem. We primarily consider the case where the same value of is used for all labels in each batch, but can be different for different batches. We also explore settings where this assumption is relaxed, including the case of sample-specine perturbations. and the scenario where only a fraction of the labels in each batch is perturbed.
The aim of the attacker is to sway the student towards its target, and so minimize the nefarious cost
1
9
(Z 60 (zxxx)))
(2)
2P
3

---

using small perturbations. For this reason, it also tries to minimize the perturbation cost
get = =a
C=
(3)
with C' a parameter expressing the cost of actions, and E(Ø")= Er (x) (z))) the expected squared error of the attacker's s target function; E indicates the average over the input distribution. We use the pre-factor E(τ") in gptr to set aside the effect of the teacher-target distance on the balance between the two costs. Note that C' is inversely proportional to the intuitive notion of attack strength: low C' implies a low cost for the action and therefore results in larger perturbations; the z-axis in Fig. 1-B shows the inverse C. The attacker's goal is to find the sequence actions a that minimize the total expected cost:
T E (o p=1
{a opt = argmin Erut lim G((aw).T)). {ap)
G=
+ 9
not
(4)
T-000
where Efut represents the average over all possible realizations the future data stream, and y E (0, 1) is the future discounting factor. In relation to make the crucial assumption that G' is dominated by the steady-state running costs; we use y = 0.995 in our experiments.
2.3 SGD dynamics under attack
The perturbed batch B = {zp, v p is used to update the model parameters 6%, following the standard (stochastic) gradient descent algorithm using the MSE loss function:
0 p+1
0%
V o2 Fu (B)))
1 Σ 2P
(
(T - )
(5)
where 7j is the learning rate. We characterize the system's 's dynamics in terms of the relative teacher- student distance, defined
(E(G)))))())))))))
(6)
Note that d = 0 (resp. d==1) 1) for a student of that perfectly predicts the clean (resp. target) labels, on average. We will split the training process into two phases: first, the student trains on clean data, while the attacker calibrates its policy. Then, after convergence of the student, attacks start and training continues on perturbed data. typical realization of the dynamics is depicted in Fig. 1-C. which shows dy for a logistic regression classifying MNIST digits during the clean-labels phase, and under attacks increasing strength (decreasing values the cost C). The sharp transition observed in Fig. I-B occurs for d o0 Rs 0.5, when the student is equally distant from the teacher and target.
2.4 Attack strategies
Finding the optimal actions sequence that solves the control problem (4) involves performing the average Eft, and so it is only possible if the attacker knows the data generating process. Even then, however, optimal solutions can be found only for simple cases, and realistic settings require approximate solutions. We consider the following approaches:
Constant attacks. The action is observation-inddeendeer and remains constant for all SGD steps: a₂ = a J. This simple baseline can be optimized by sampling data streams using past observations, simulating the dynamics via Eq. (5), and obtaining numerically the value of a that minimizes the simulated total expected cost.
Greedy attacks. A greedy attacker maximizes the immediate reward. Since the attacker actions have instantaneous effect on the learner, the greedy objective has to include the next training step. The greedy action is then given by
d (Trps 0 7) argmin Erg+t
[op + Ait
The average Exy,1 can be estimated with input data sampled from past observations, and using (5) to obtain the next student state. Similarly to constant attacks, the greedy future weight o can be calibrated by minimizing the simulated total expected cost using past observations.

---

Reinforcement learning attacks. The attacker can use parametrized policy function a(z, 8*) and optimize it via reinforcement learning (RL). This is model free approach, and it suitable for grey box settings. Tuning deep policies is computationally costly, however, and it requires careful calibrations. We utilize TD3 [22], a powerful RI. agent that improves the deep deterministic
policy gradient algorithm [23]. We employ TD3 as implemented in Stable Baselines3 [24].
Clairvoyant attacks. A clairvoyant attacker has full knowledge of the future data stream, so simply looks for the sequence {a,} that minimizes G G((a,): ) > 1). Although the clairvoyant setting is not realistically plausible, provides an upper bound for the attacker's performance in our experiments. We use Opty [25] cast the clairvoyant problem into a standard nonlinear program, which is then solved by an interior-point solver (IPOPT) [26].
The above attack strategies are summarized as pseudocode in Appendix A.
3 Theoretical analysis
We first analyze online label attacks with synthetic data establish theoretical results. We will confirm our findings with real data experiments Sec. 4.2. Solving the stochastic optimal control problem (4) is very challenging, We discuss an analytical treatment in two scenarios for the linear TSA problem with unbounded action space, where
for simple architectures Φ(x, f) and assuming that Pa is known.
6<:; w) w x/VDD.
(8)
3.1 Large batch size: deterministic limit
In the limit of very large batches, batch averages of the nefarious cost g and loss L, in Eqs. (2, 5) can be approximated with averages over the input distribution. For standardized and i.i.d. input elements, the resulting equations are
pef
2D Iu w² V - ((w w²) + (w)) wn )ay)
(9)
In this setting, the attacker faces deterministic optimal control problem, which can be solved using Lagrangian- based method. Following this procedure, we obtain explicit solutions for the steady-state student weights w and optimal action dopt. The relative distance dept between student and teacher then follows from Eq. (6). We find
(10) The above result is intuitive: the student learns function that approaches the attacker's target as the cost of actions C tends to zero, and (C 0) Vice versa, for increasing values of C, the attacker's 's optimal action decreases, and the student approaches the teacher function.
[RESULT 1]
w = ~0 + dop'
- (w--w")
dopt = a = (C+1)-1
In the context of classification task, accuracy of the student Aμ,C, P) = [z]),, with S₁ (z) = (sign (of, (z)) + dign(o"(=))) /2. For label- flippiingngggggg attacks, where o* = - direct consequence of Eq. (10) is that the steady-state accuracy of the student exhibits discontinuous transition in C 1. More precisely, we find
characterize the system dynamics in terms of the
[RESULT 2]
AC) 1 H(C
(11)
with H(-) the Heaviside step function. This simple result explains the behaviour observed Fig. I-B, where the collapse in accuracy occurs for attack strength C-1 x 1. We refer to Appendix B for a detailed derivation of results (10, 11).
3.2 Finite batch size: greedy attacks
When dealing with batches of finite size, the attacker's optimal control problem stochastic and has no straightforward solution, even for the simple linear TSA problem. To make progress, we consider greedy attacks, which are computationally convenient and analytically tractable. While an explicit solution to (7) is generally hard to find, it is possible for the linear case of Eq. (8).
5

---

A.
B.
D.
10
1.0
1780 1980110 03
accuracy
15 0.5
0.5
P=1
%
o
P-10
Px10
0.0
... 91oory
mea:: 0.27
-1
8-1
100
200
-2
2
250
500
logio(C)
#
Figure 2: Greedy and clairvoyant attacks in the linear TSA problem. A: relative distance vs SGD step μ for greedy attacks on linear models for two different batch sizes P. Solid lines display the average du, shaded areas cover 1std of dy. Dashed lines show the theoretical estimate of Eqs. (13). B: steady-state average accuracy of the student vs cost of action. The dashed line shows the theoretical prediction of Eq. (11). C: scatterplot of greedy (G) vs clairvoyant (CV) actions used on the same data stream with P 1. D: student-teacher (s-t, green) and sudent-target (s-*, coral) overlap vs SGD step, for the clairvoyant (dotted line) and greedy (continuous line) attacks of panel C. Parameters: C 1, a E 22 D 10, " 0.02 x D. Input elements sampled i.i.d. from Pa = No 1).
We find the greedy action policy
P (w w0) "-0=""""'ppp xx))" w²)"xx + O(n).
(12)
CDP
Note that a decreases with the cost of actions, and a + for C + oo. With a policy function at hand, we can easily investigate the steady state of the system by averaging over multiple realizations of the data stream. For input elements sampled i.idd from Pa = NO0, 1), we find the average steady-state weights ui.
[RESULT 3]
Thx w² + d dol w'),
(w",, ds 2S=((p)) P PP22
C c+1)
(13)
where JG is the distance (6) of the average steady-state student; we refer to Appendix C for the derivation of the above result. The expression of dg includes surprising batch-size effect: for fixed value of the cost C, greedy attacks become more effective for batches of decreasing sizes, as the weights get closer w" while perturbations become smaller (see Eq, (45)). This effect is displayed in Fig. 2-A, which shows d, vs SGD step for greedy attacks, and for P = 1, 10. Note that only the perturbed training phase shown, so do 0 as the student converges to the teacher function during the preceding clean training phase. The black dashed lines correspond to the steady-state values given by (13), which are in very good agreement with the empirical averages (up to a finite-n effect)*. We also observe that dy is characterized by fluctuations with amplitude that decreases as the batch size increases. A consequence of such fluctuations that the average steady-state accuracy of the student undergoes a smooth transition. The transition becomes sharper as the batch size increases, and in the limit P > oc converges to the prediction (11); see Fig. 2-B, which shows numerical evaluations of Ax (C, P) averaged over multiple data streams. In our experiments, we draw the teacher weights elements as i.i.d. samples from (0, 1) and normalize them so that | 12 = D, while w" = =-
Remark. In order to derive the result of Eq. (13), we have set न D/n that dS dept for P > 20 (see Appendix I. This guarantees the steady-state optimality of the greedy action policy in the large batch limit. Note that 7 coincides with the timescale of the linear TSA problem, and it lends itself to a nice interpretation: in the greedy setting, where the horizon ends after the second training step, the future is optimally weighted by factor proportional to the decorrelation time of the weights. Optimality for P finite is not guaranteed, though we observe numerically that 5 approximately matches our choice even for theoretical results of the next two sections.
1, 10. We use again D/n to obtain the
We shall remark that the quantities JS and J... = lim, (dz,). the average over multiple data streams shown in Fig. 2-A, can, in general, differ, and they only coincide necessarily in the deterministic limit P

---

3.2.1 Sample-specifie perturbations
The batch-size effect observed for greedy attacks can be explained as signature of the batch average appearing in the policy function (12). When dealing with single data point time, the attacker has precise control over the data labels, designing sample-specific perturbations. For batches with multiple samples, instead, perturbations are designed to perform well on average and do not exploit the fluctuations within the data stream. As result, attacks become less effective, increasing in magnitude and leading to a smaller average steady-state distance between the student and the teacher function. A straightforward solution to this problem consists of applying sample-specine perturbations, thus using a multi lulti-dimmensioal control a E IR",, which, however, results in a higher computational cost. This can be achieved by using the policy function (12) independently for each sample, so that the p-th element of a given by
50 1 (w (ou--")"" =²)
( xxp xp(w' -w")
w²) " Tp.
(14)
In Appendix C.1, we show that this strategy coincides with the optimal greedy solution for multi- dimensional, sample-specific control, up to corrections of order We also show that the resulting average steady state reached by the student, for normal and i.i.d. input data,
[RESULT 4]
wh w² d Aw
= -C/3 +)
(15)
Remarkably, there is no batch-size size dependence in the above solution, and the average steady-stabe distance coincides with (13) for P = 1. This result demonstrates that precise, sample-specin greedy attacks remain effective independently of the batch size of the streaming data.
3.2.2 Mixing clean and perturbed data
In the previous section, we addressed a case of enhanced control, where batch perturbations are replaced by sample-specific ones. Here, instead, consider case of reduced control, where the attacker can apply the same perturbation to fraction of the samples in each batch. This scenario can arise when the attacker faces computational limitations environmental constraints. For example, the streaming frequency may be too high for the attacker to contaminate all samples at each time step, or, in poisoned federated learning setting, the central server could have access a source of clean data, beyond the reach of the attackers. Concretely, we assume that the attacker has access to a fraction p of the batch samples only. Therefore, training involves pP perturbed and (1 P)P clean samples. Perturbations follow the policy function
pP
G 0x
Au Aw Tup + O())-
(16)
CDpP
In Appendix C.2, we find the following average steady-state solution for normal and i.i.d. input data:
[RESULT 5]
Th = w -dd
dc =
(17)
see Fig. 7 for a comparison with empirical evaluations. Note that for large batches dG (C/p+1)-+ indicating that the cost of actions effectively increases by factor p-1, We remark that the above result is derived under the assumption that the attacker ignores the number of clean samples used during training, so it cannot compensate for the reduced effectiveness of the attacks.
4 Empirical results
4.1 Experiments on synthetic data
Having derived analytical results for the infinite batch and finite batch linear TSA problem, we now present empirical evidence as to how different strategies compare on different architectures. As a first question, we investigate the efficacy of greedy attacks for data streaming in batches of small size. By choosing appropriate future weight 7, we know the greedy solution is optimal as the batch size tends to infinity. To investigate optimality the finite batch setting, we compare greedy actions with clairvoyant actions the same data stream, optimizing 7 over grid of possible values. By
7

---

A. Linear regression
B. Sigmoidal perceptron
2-layer NN
1.0
1.0 1
0.5
0.5
rg 0.5
P=1
P=1
P=1
P-10
P=10
P-10
0.0
2
logia(C)
logiol (C)
log:o(C)
1.0
1.0
1.0
8
14
ha
0.5
0.5
0.5
X
0.0
0.0
0.0
C RL CV
C RL G CV
RL* G CV
C: constant,
RL: reinforcement learning,
G: greedy,
CV: diairvoyant
Figure Empirical results for the TSA problem with synthetic data. A, top panel: average steady-state distance vs cost of action C' for the linear TSA problem and greedy attacks. The orange area represents the range of solutions of dG (13) for P E [1, 10]. Bottom panel: average steady-state running cost of different attack strategies relative to the largest one (constant attacks), for P' = 1, and C'= 1. B, C: same quantities as shown in A for the perceptron and NN architectures; RL* indicates an agent that sees the final layer only. Averages were performed over 10 data streams of 10 batches and over the last 10 steps for each stream. Parameters: D = 10, 7 = 0.02 x D, a E 2- 3] (A, B), M = 100, = 0.02 x D X v M, a E [0, 1] (C). Input elements sampled i.i.d. from Pa = (V
definition, clairvoyant attacks have access all the future information and therefore produce the best actions sequence. The scatterplot in Fig. 2-C shows greedy vs clairvoyant actions, respectively a and CV, on the same stream. Note that greedy actions are typically larger than their clairvoyant counterparts, except when CV is very large. This is distinctive feature of greedy strategies as they look for local optima. The clairvoyant vision allows the attacker allocate its resources more wisely, for example by investing and paying extra perturbation costs for higher future rewards. This is not possible for the greedy attacker, as its vision is limited to the following training step. Substantially, though, the scattered points in Fig. 2-C lie along the diagonal, indicating that greedy attacks are nearly clairvoyant efficient, even for P identical greedy and clairvoyant trajectories of the student-teacher and student-target weights overlap, defined respectively as O = w T w² /D and O = w T "'' / (see Fig. 2-D).
The match between a and a CV corresponds to almost
Next, we investigate the steady state reached by the student under greedy attacks and the performance of the various attack strategies for three different architectures: the linear regression of Eq. (8), the sigmoidal perceptron ((x; w) = (xf(2/v2), with Erf(-) the error function and 2 = w x/ /D, and the 2-layer neural network (NN)
M
1 VM
ol w)
Σ m=1
Um Frf(fe//// /V2),
Zm. = Wm VD,
(18)
with parameters W.m RRD and e E R We continue to draw all teacher weights from the standard normal distribution, normalizing them to have unitary self-overlap. For the perceptron we set the target weights as w" = - w", while for the neural network w = wh, and v* = -.' The top row in Fig. 3 shows dxc = lim (dd)), i.e. the average steady-state distance reached by the student versus the cost of actions C for greedy attacks. The solid lines show the results obtained from simulations The yellow shaded area shows de form Eq. (13) comprised between values of batch size P = 1 (upper contour) and P = 10 (lower contour). Note that the three cases show very similar behavior of doo (C, P) and are in excellent agreement with the lincar TSA prediction.
'Practically, this involves solving numerically the minimization problem in Fq. (7) on a discrete action grid the range [amin. [max]. This is done at each SGD step μ. and requires simulating the transition μ - μ + 1 estimate the average nefarious cost [g(p] sampling input data from a buffer of past observations.
8

---

In order to compare the efficacy of all the attack strategies presented in Sec. 2.4, we consider the running cost, defined as 9n. = gfte + qm More precisely, we compute the steady-state average Doc over multiple data streams. The bottom row in Fig. 3 shows this quantity for the corresponding architecture of the top row. The evaluation of the clairvoyant attack missing for the NN architecture, as this approach becomes unfeasible for complex models due to the high non-convexity of the associated minimization problem. Similarly, reinforcement learning attacks are impractical for large architectures. This is because the observation space of the RL agent, given by the input z and the parameters of the model under attack, becomes too large to handle for neural networks. Therefore, for the NN model we used a TD3 agent that only observes the read-out weights of the student network; hence the asterisk in RL We observe that the constant and clairvoyant strategies have respectively the highest and lowest running costs, as expected. Greedy attacks represent the second-bee best strategy, with an average running cost just above that of clairvoyant attacks. While we do not explicitly show it, it should also be emphasized that the computational costs of the different strategies vary widely; in particular, while greedy attacks are relatively cheap, RL attacks require longer data streams and larger computational resources, since they ignore the learning dynamics. We refer to Fig. 8, 9 in Appendix D for a comparison between greedy and RL action policies, and for a visual representation of the convergence in performance of the RL algorithm vs number of training episodes.
4.2 Experiments on real data
In this section, we explore the behaviour of online data poisoning in an uncontrolled scenario. where input data elements are not i.i.d and are correlated with the teacher weights. Specifically, we consider two binary image classification tasks, using classes 'I' and '7' from MNIST, and 'cats' and 'dogs' from CIFAR10, while attacks are performed using the greedy algorithm. We explore two different setups. First, we experiment on the MNIST task with simple architectures where all parameters are updated during the perturbed training phase. For this purpose, we consider logistic regression (LogReg) and a simple convolutional neural network, the LeNet of [27]. Then, we address the case of transfer learning for more complex image-recognition architectures, where only the last layer is trained during the attacks, which constitutes typical application of large pre-trained models. Specifically, we consider the visual geometry group (VGG11) I) [28] and residual networks (ResNet18) [29]. with weights trained the ImageNet- Ik classification task. For all architectures, we fix the last linear layer to have 10 input and output features, followed by the Erf activation function.
Preprocessing. For LogReg, we reduce the dimensionality of input data to 10 via PCA projection. For LeNet. images are resized from 28x28 to 32x32 pixels, while for VGG11 and ResNet18 images are resized from 32x32 to 224x224 pixels. Features are normalized to have zero mean and unit variance, and small random rotations of maximum 10 degrees are applied to each image, thus providing new samples at every step of training.
Learning. The training process follows the TSA paradigm: we train a teacher network on the given classification task, and we then use it to provide (soft) labels to a student network with the same architecture. As before, we consider two learning phases: first, the attacker is silent, and calibrates 5. Then attacks start and the student receives perturbed data. For consistency with our teacher-studens analysis, we consider the SGD optimizer with MSE loss; see Fig. 10 in Appendix D for a comparison between SGD and Adam-based learning dynamics. To keep the VGG11 and ResNet18 8 models in a regime where online learning is possible, we use the optimizer with positive weight decay.
The findings are presented in Fig. 4, where panels A and B represent the outcomes of the full training and transfer learning experiments, respectively. Each panel consists of two rows: the top row displays the dependence of the relative student-teacher distance on the cost of action C and batch size P. The orange area depicts dS from Eq. (13) for P e [1, 10). which we included for a visual comparison. The bottom row shows the corresponding average steady-state accuracy of the student. In general, all learners exhibit comparable behavior to the synthetic teacher-student setup in terms of the relationship between the average steady-state distance dxc and C. Additionally, all experiments demonstrate a catastrophic transition in classification accuracy when the value of C' surpasses a critical threshold. The impact of batch size P on the d.c is also evident across all experiments. The effect of the weight decay used in the transfer learning setting is also visible: the value of d remains larger than zero even when C' is very large (and attacks are effectively absent). Similarly, for very low values of C, the relative distance remains below 1. We note that calibrating 7 takes a long time for complex models updating all parameters, so we provide single-run evaluations for LeNet.
9

---

A. Full training MNISTT
Transfer learning CIFAR10
LogReg
LeNet
VGG11
R8sNet18
1.0
1.0
1.0
1.0
r6 0.5
0.5
r6 0.5
0.5
0.0
0.0
0.0
-2
2
2
loguo( C))
logio(C)
logio!C)
logio! C)
1.0
1.0
socuracy
socuracy
0.5
0.5
0.5
0.5
P-1
P-1
0.0
P=10
P-10
-2
logio(C)
logio(C)
logiol C)
logio(C)
Figure 4: Empirical results for the TSA problem with real data. A, top row: average steady-state distance vs cost of action C, for greedy attacks on fully trained logistic regression (LogReg) and LeNet architectures. The orange area represents the range of solutions of & (13) for P E [0]. repress
Bottom row: average steady-state accuracy vs C' for the architectures of the top row. B: same quantities as shown in for transfer learning experiments on VGG11 and ResNet18. Averages were performed over 10 data streams of 10 batches and over the last 103 steps for each data stream. Parameters: D 10, r = 0.02 x (LogReg, VGG11, ResNet18), rj = 0.01 (LeNet), a E 10.
5 Conclusions
Understanding the robustness of learning algorithms is key their safe deployment, and the online learning case, which we analyzed here, is of fundamental relevance for any interactive application. In this paper, we explored the case of online attacks that target data labels. Using the teacher-student framework, we derived analytical insights that shed light on the behavior of learning models exposed to such attacks. In particular, we proved that discontinuous transition in the model's accuracy occurs when the strength of attacks exceeds a critical value, as observed consistently in all of our experiments. Our analysis also revealed that greedy attack strategies can be highly efficient in this context, especially when applying sample-specific perturbations, which are straightforward to implement when data stream in small batches.
key assumption of our investigation is that the attacker tries to manipulate the long-run behavior of the learner. We note that, for complex architectures, this assumption may represent computational challenge, as the attacker's action induces a slowdown in the dynamics. Moreover, depending on the context, attacks may be subject time constraints and therefore involve transient dynamics. While we have not covered such a scenario in our analysis, the optimal control approach that we proposed could be recast in finite-time horizon setting. We also note that treatment of online data poisoning did not involve defense mechanisms implemented by the learning model. Designing optimal control attacks that can evade detection of defense strategies represents important avenue for future research.
Further questions suggested by results. While the qualitative features of our theoretical predictions are replicated across all real-data experiments that we performed, we observed differences in robustness between different algorithms. For standard, test-time adversarial attacks, model complexity can aggravate vulnerability [30, 31], and whether this happens in the context of online attacks represents important open question. Another topic of interest is the interaction of the poisoning dynamics with the structure of the data, and with the complexity of the task. Finally, we remark that our analysis involved sequences of i.i.d. data samples: taking into account temporal correlations and covariate shifts within the data stream constitutes yet another intriguing challenge.
Compute. We used single NVIDIA Quadro RTX 4000 graphics card for all our experiments.
10

---

Acknowledgements
SG and GS acknowledge co-funding from Next Generation EU, in the context of the National Recov- ery and Resilience Plan, Investment PE1 Project FAIR "Future Artificial Intelligence Research". This resource was co-financed by the Next Generation EU [DM 1555 del 11.10.22].
References
1. Huang, L., Joseph, A. D... Nelson, B., Rubinstein. B. I. & Tygar, J. D. Adversarial Machine Learning, Proceedings of the 4th ACM Workshop on Security and Artificial Intelligence, 43-58 (2011).
2. Biggio, B. & Roli, F. Wild patterns: Ten years after the rise of adversarial machine learning. Puttern Recognition, 317-331 (2018).
3. Chen, X., Liu, C., Li, B., Lu, K. & Song, D. Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning. Preprint, ArXiv:1712.05522 (2017).
4. Gu, T., Liu, K., Gavitt,, B. & Garg, S. BadNets: Evaluating Backdooring Attacks Deep Neural Networks. IEEE Access, 47230-47244 (2019).
5. Goldblum, M. et al. Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks,
and Defenses. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1563-1580 (2023).
6. Zhang, X., Zhu, X. & Lessard, L. Online Data Poisoning Attacks. Proceedings of the 2nd Conference on Learning for Dynamics and Control, 201-210 (2020).
7. Gardner, E. Derrida, B. Three unfinished works on the optimal storage capacity of networks. Journal of Physics A: Mathematical and General, 1983 (1989).
8. Seung, H. S., Sompolinsky, H. & Tishby, N. Statistical mechanics of learning from examples. Physical review (1992).
9. Engel, A. & Van den Broeck, C. Statistical mechanics of learning (2001).
10. Carleo, G. et al. Machine learning and the physical sciences. Reviews of Modern Physics (2019).
11. Biggio, B., Nelson, B. & Laskov, P. Poisoning Attacks against Support Vector Machines. Proceedings of the 29th International Coference on Machine Learning, 1467-1474 (2012).
12. Xiao, H. al. Support vector machines under adversarial label contamination. Neurocomputing.
53-62 (2015).
13. Muñoz-González, L. et al. Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization. 10th ACM Workshop on Artificial Intelligence and Security, 27-38 (2017).
14. Ma. Y., Zhang, X., Sun, W. Zhu, X. Policy Poisoning in Batch Reinforcement Learning and Control. Proceedings of the 33rd International Conference Neural Information Processing Systems (2019).
15. Mei, S. & Zhu, X. Using Machine Teaching to Identify Optimal Training-Set Attacks on Machine Learners. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2871-2877 (2015).
16. Wang, Y. & Chaudhuri, K. Data Poisoning Attacks against Online Learning. Preprint, ArXiv:1808 08999 (2018).
17. Pang, T., Yang, X., Dong, Y., Su, H. Zhu, Accumulative Poisoning Attacks on Real-time Data. Advances in Neural Information Processing Systems, 2899-2912 (2021).
18. Liu, W. et al. Iterative Machine Teaching, Proceedings of the 34th International Conference Machine Learning, 2149-2158 (2017).
19. Lessard, L.,, Zhang, X. & Zhu, X. An Optimal Control Approach to Sequential Machine
Teaching. Proceedings the Twenty-Second International Conference on Artificial Intelligence and Statistics, 1495-2503 (2019).
20. Lee, S., Goldt, S. & Saxe, A. Continual Learning in the Teacher-Student Setup: Impact of Task Similarity. Proceedings of the 38th International Conference on Machine Learning, 6109-6119 (2021).
21. Yang. Z. et al. Understanding Robustness in Teacher-Student Setting: A New Perspective. Preprint, ArXiv:2102.1 13170 (2021).
22. Fujimoto, S., van Hoof, H. Meger, D. Addressing Function Approximation Error Actor- Critic Methods. Preprint, ArXiv:1802.09477 (2018).

---

23. Lillicrap. T. P. et al. Continuous control with deep reinforcement learning. 4th International Conference on Learning Representations, ICLR (2016).
24. Raflin, A. et al. Stable-Basclines:: Reliable Reinforcement Learning Implementations. Journal
of Machine Learning Research, 1-8 (2021).
25. Moore, J. K. & van Bogert, A. D. Opty: Software for trajectory optimization and parameter identification using direct collocation. Journal of Open Source Software (2018).
26. Wächter, A. & Biegler, L. T. On the Implementation of an Piteri Filter Line-Search Algorithm for Large-Scale Nonlinear Programming. Muthematical Programming, 25-57 (2006).
27. LeCun, Y. Bottou, L.,, Bengio, Y. & Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 2278-2324 (1998).
28. Simonyan, K. & Zisserman, Very Deep Convolutional Networks for Large-Scar Scale Image Recognition. 3rd International Conference on Learning Representations, ICLR (eds Bengio, Y.
& LeCun, Y.) (2015).
29. He, K., Zhang, X., Ren, & Sun, J. Deep Residual Learning for Image Recognition. IEEE Conference Computer Vision and Pattern Recognition (CVPR), 770-778 (2016). 30. Tsipras, D., Santurkar, S., Engstrom, L.., Turner, A. & Madry, A. Robustness may be at odds with accuracy. Preprint, ArXiv:1805.12155 (2018).
31. Carbone, G. el al. Robustness of bayesian neural networks to gradient-based attacks. Advances in Neural Information Processing Systems, 15602-15613 (2020).
32. Bressan, A. & Piccoli, B. Introduction to the mathematical theory of control (2007).
12

---

A Attack strategies: algorithms
Table summarizes the attack strategies introduced in Sec. 2.4. For clarity, we present the algorithms for data streaming in batches of size P = 1. We recall that the action value a of constant attacks and the greedy future weight ý can be optimized by sampling future data streams from past observations, and using the SGD update rule (5) to simulate the future dynamics. Similarly, the attacker can sample past observations to calibrate the RL policy (x,
Algorithm 1 Online label attacks (batch size P
Constant attacks
Reinforcement learning attacks
1: optimize d
1: calibrate policy a azL(2z, 0)
2: repeat
2: repeat
3:
au a
3: observe clean batch (x,, v') state 8
4: y b + (y 2/
Qn a 0%)
5:
V & (z 0x)
5: up + y + [yp 1/
6:
0 fat1 t 0% Vv Cly 8/.)
6: Up + ( (2)
7: until end of stream
7: f j++1 + t% VV og [(, V/)
8: until end of stream
Greedy attacks
1: optimize
Clairvoyant attacks
2: repeat
1: observe state 0j, stream S = [xx, )
3: observe clean batch (x, y²) ) state "
2: find {a, y argmin G(S, 09)
4: an + argmin(g) + 79
3: repeat
5: y v (vg
y
4: V 1/. + (y v
6: Vi & (Iμ (p)
5: Vr + (I
7:
fa+1 < fa V Clyf,
#a+11 + 0% nV L(y v/2)
8:
until end of stream
until end of stream
B Linear TSA problem: optimal solution
In the limit of very large batches, batch averages of the nefarious cost opet and loss L. in Eqs. (2, 5) can be approximated with averages the input distribution. For a general architecture ø. and indicating with t, s, and x the teacher, student, and attacker's target, respectively, we can write
In (Lp(s.)) s) - (s, *) Ia(*,*))
(19)
1 V L. 2 [[,ssss) [s (1 a,)) (s, (s,+))or +)a
(20)
where l(a.b) Ex (x) (x)) for two models, a and b, with the same architecture but different parameters 00, 0², and /' 1. In this case, the optimal control problem (4) is deterministic, and can write in continuous time 0)
opt argmin / dun (gper + guef) )
(21)
where op-r== = 22 Note that μ is continuous time index, and the above minimization problem considers all functions 0g E [Amin amax] for [0, oo). In the following, that the action space is unbounded, i.c. an E (-o0, oo), and that the elements of x are i.i.d. samples with zero mean and variance o², In the linear TSA problem, where Φ(2; w) = TTx ie/VD, DD, the above
will assume
Eqs. (19, 20) simplify to
02
0² (Awft Aw
gu
A A
Va Cp
(22)
2D
D
13

---

where Aw = w" - -w=,, w=,,ndd and 1 the squared 2-norm. We also find
0² 1 A PCC.
Ö =
(23)
We shall recall that in the TSA problem each batch is used only once during training. This assumption guarantees that imputs zn and weights w are uncorrelated, a necessary condition to derive the above expressions. We solve this problem with Lagrangian- approach: the Lagrangian L is obtained by imposing the constraint w = - Ly.. at all times, with the co-state variables Ay. R
Jo dur (opt + +H (1 + 0² (Aw *ww"*ap) /D).
L 1=
(24)
The Pontryagin's 's necessary conditions for optimality 0a,, = O, (0wz 0, 0, and 0x == 0 give the following set of equations coupling aus wf, and Ap:
1* - -x
= 0,
) / / D + Xp - -222 = 0,
i + (A + aw / = O.
(25)
The above system of ODEs can be solved by specifying the initial condition w and using the transversality condition y-mp-oo Av = 0. At steady state, we obtain the following equation for u
Aust o² Au Aw Aw IČD 0,
(26)
which admits only one (optimal) solution. We find it as a linear combination of w and w
w = 2x Aw"
opt = (C+
(27)
From the definition of d, (6), it follows that
jppt
opt 0 60
(28)
As final remark, we observe that the same procedure can in principle be applied to TSA problems with non-linear architectures, as long as an explicit expression for I(a, b) is available. However, one may find multiple steady-state solutions, and obtaining guarantees for optimality is often hard [32].
B.1 Optimal greedy solution
For the linear TSA problem, and in the limit of large batches, the discreteetime equation (7) for greedy actions simplifies to
G dy
= argmin an
Ca 2
0² +7 $ 1 ( (an) w= w²13
(29)
2n
The expression of w (ap) is given by the update rule, which can be conveniently written as
wh+t = U1 + U2a
(30)
noo Aw D, and U2 -n0² Aw "Dt /D. The solution of (29) gives the greedy where 81 wh
policy function
w
T U/2 21 T02
G a
(31)
+ |12|2
The right-hand side of the above equation depends on the future weighting factor 7. Requiring that the (greedy) update rule w Ui + v2a gives the optimal steady-state solution of Eq. (27), and using the explicit expression of Ò (23), one finds the optimal weight
F D/031 n7
(32)
14

---

B.2 Accuracy cost of action
In Sec. 3.1, we addressed the case of attacks in classification context, with class labels given by the sign of o² (a:), and where the attacker aims to swap the labels, so Ø² = =o' A pointwise estimate of the accuracy given by
(x) = 2 (x) + sign(
(33)
and the system dynamics can characterized by the accuracy of the student, defined as (, P) [x)],, with Eg the average over the input distribution. For the linear TSA problem, have w = --w,, w", and, consistently with the definition of du (6),
=
w = w² + du(w" w²) = (1 - 2dw)w².
(34)
follows that (x) for d, S 0.5, and (x) otherwise. the deterministic limit of large batches, the optimal steady-state solution (27) gives
(x) sign (C 1) w' 2) + sign (w'' (u'"z))
(35)
We then have Sex 0 for C' < and Six 0 otherwise, regardless of the value of x, giving
- -
(36)
with H-) the Heaviside step function.
C Stochastic control with greedy attacks
When the batch size P is finite, the attacker's optimal control problem stochastic and has no straightforward solution, even for the simplest case of the linear TSA problem. It is however possible to find the average steady-state solution for greedy attacks, as we show in this Appendix. We derived the greedy policy in B.1 for P oc, and for i.i.d. input elements with zero mean and variance o². For general P, the same expression (31) holds, with vn and U2 now given by
P
1i = w 1) DP
Aw i znd) Zaps
p=1
U2 -1 DP
DP
Awota
Iup)
Kup:
(37)
where aw = w" - wh The first-order expansion of ag in powers of reads
a
Awse'
Aw Tpp O(1),
(38)
CDP
where we have used 7 = D/o2n. which guarantees that in the limit P - oo we recover the optimal solution (27). We can the above action policy in the SGD update rule (30) and take the average over data streams to get the steady-state equation
1
Amst ool
PTu + P(P - 11Tmm))
(39)
CDP2
where we have imposed
प. Th #+1 Th for and where
Tı Ex (Awwse
BeeT rAw x) (Aw xm.I)
(40)
(Awie TrAuteT xx) (Aw x r'ar))
T Tool Exzta
(41)
Note that for P = 1 and P -> oo the right-hand side of (39) only involves Tir and Toat, respectively (hence the labels). So far, we have assumed that input elements are i.i.d. samples from P. with first two moments my 0, and m2 o². We also recall that zn and wf. are uncorrelated, as each
15

---

1.0
Figure Average steady-state greedy action. 0g vs cost of actions C for the linear TSA problem with (O 1). The orange area represents the range of solutions (45) for E [0, The red and blue lines show empirical evaluations for P = 1 and P 10, respec-
P=1
8 0.5
tively. Parameters: = 10, 7j = 10 x D, a E [-2, 3). Averages performed over 10 data streams of 2 batches, and over the last 10 steps each stream.
0.0
-2
2
logio(C) C)
batch is used only once in the TSA problem. We now further assume that input elements have third and fourth moments my = and m4 < oc. It then immediate to verify that Tur = Turmm,, ma) and oot T oz (m22) showing that finite batch-size effects depend on the kurtosis of the input distribution. Specifically, we find
Tu = (m1 -3m -3m))Aw AW + m2 Aw" 1 A + 2mz Aw
T = m
A A Awf".
(42)
For Pa -N(0, 1), the first term in Tn disappears, and the above expressions simplify
Tı Aw t 2A
Am Awf",
T Aw. A
(43)
Substituting in Eq. (39) the expressions of Tut, Toet, and Ö from (23), and looking for a solution of Th as linear combination of w² and w", we find
P (==((pr) PP22 C+ c+1) -1
ds -==
Th = r - d A
(44)
Note that d is the relative distance (6) of the student with parameters wh From this result, can easily find the mean steady-state greedy action by averaging (38) over data streams, giving
S(P)
I(P) = P/(P 22)
(45)
+(P)C+1'
Fig. shows a comparison of the above result with empirical evaluations, which are in excellent agreement. Together, (44) and (45) demonstrate that greedy attacks become more efficient as the batch size decreases, reducing the distance between the student and the target while using smaller perturbations. We remark that this result is derived using the expression of 7 from the P - co analysis, as Eq. (32). our experiments, this value near-optimal also for finite for linear learners, while for non-linear architectures it provides good first guess during the calibration phase.
C.1 Sample-specifie perturbations
In this section, address the case where the attacker has finer control over the data labels and can apply sample-specific perturbations, rather than batch-specific ones. The control variable is P-dimensional, with P the size of the streaming batches, and each label y is perturbed
4/ = vp(1 - ap) + u/
(46)
while the perturbation cost is g.er = C/app 1/2P. We can write the SGD update rule as
1 Σ
w
Vip + U2papp
(47)
p=1
where now
Uip = : 17 (AA
st kpp)
Zypl D, U2p -1) (Awzr xpp) Tppl D.
(48)
16

---

1.0
Figure 6: Relative distance with sample-specific attacks. Student-teacher distance vs SGD step for the linear TSA problem with i (0 1). The light-red and blue lines show single realization of the dynamics for vatch-specife control. The dark-red line shows the same quantity for sample-specific,
33 0.5
P=1
P=10
P=10
multi-dimensional control. Parameters: C = 1, D 10.
0.0
= 1010-- D, a [-2.3]
2000
4000
We use again the notation Aw wd - w² Note that (47) reduces to (30) when the control variable one-dimensional and batch-specific, i.e. Opp On p. The minimization problem (7) for greedy actions now consists of P coupled equations, one for each control variable Opp- For i.i.d. input elements with zero mean and variance o², we find
= argmin Pup
Claml + + 2D
o²
W w (ap) w²1
(49)
kp
2
and the first-order conditions lead to
o² Capp + +
P
Σ
T vij
any
w"
U2p 0.
(50)
A straightforward and explicit solution can be found by considering only the first-order terms in effectively decoupling the above system of equations. With 7 D/o², we obtain
1
A. T Amp
Epp
(51)
ČD
which coincides with the P=1 solution for batch batch-specifer specific greedy attacks (38). We can now use this policy in the update rule (47) to investigate the steady state of the system. Once more, we average across data streams with i.i.d. data sampled from Pa (0, 1) and impose that the average student weights w reach steady state for + oc. This leads to the following i--independent solution
The = w² de JG Aw
ds (C/3+1)
(52)
Fig. 6 shows empirical evaluations confirming this result. Finally, averaging the policy function (51) across data streams and using the above result for w we find
1/3
(53)
cop
C/3+1
C.2 Mixing clean and perturbed data
The assumption that the attacker can perturb every data sample in each batch may not always be satisfied. For example, in a federated learning scenario, the central server coordinating the training may have access to a trusted source of clean data that inaccessible the attacker. Moreover, the attacker may face a limited computational budget and only be able to process fraction of samples in the data stream each timestep. Here, we consider the case where only fraction p of the samples in each batch is perturbed by the attacker. Moreover, we assume that the attacker ignores the amount of clean samples used for training. Precisely, the attacker considers the update rule
w #++1 = wi Vuz (BePt)
oP
OP
(54)
Σ (Aun' xpp) Eyp + ag
A Austall T Tup) Fpp)
DpP
with pP perturbed samples, while training follows
w = w/j V Ly (B.Pt) 17(1 - V) Cu (B(--))))
(55)
w/f DP
Σ Awsst znd) Ixp + ag Σ Awite" xup)) I4z
17

---

Figure 7: Mixing clean and poisoned samples. Average steady- state distance fraction p of poisoned samples. under greedy attacks. The dashed line shows the estimate of Eq. (58), and the red dots display the associated empirical evaluations. Blue crosses show empirical results obtained for logistic regression training on MNIST digits. Parameters: C' = 1, P 100,
0.4
0.2
x
Theory LinReg syn.
x
LogReg MNIST
10, 0.1, E |-2,3], 3j. Averages performed over 10 data streams of 10 batches, and over the last 10 steps in each stream.
0.0
0.2
0.4
0.6
0.8
1.0
thus involving pP perturbed samples and (1 - P) clean samples. We recall that Aw w w and that the stream has input data drawn i.i.d. from Pa. Following (54), the greedy policy (38) in this case reads
pp
= CDpP
AusT
Eup Tup + O(n).
(56)
We now substitute the above expression into (55) to investigate the steady state of the system. As before, we can obtain a steady-state condition for i by averaging across data streams and imposing wi # w for μ We find
(PPTu++ pPppppPppP-- pP(pP-1)T=a))
Au xot
(57)
CDpp2
with Tir and Toot as in (43) for Pa = 10, is then immediately verified that
(( (1F+2)+1)
P pp+2
w = w de Am
d
(58)
Note that for large batches (pP >> 2) the above result reduces to dL se (C/p+1)-1 and it has simple and intuitive interpretation: when perturbations contaminate fraction p of the batch samples only, the cost of actions effectively increases by a factor p 1 Fig. 7 shows the average steady distance reached by the student model function of p. demonstrating that empirical evaluations using synthetic data perfectly match the theoretical estimate Eq. (58). We also performed real data experiments using MNIST images (as in Sec. 4.2), which again exhibit good qualitative agreement with our theoretical result.
D Supplementary figures
Greedy policy
B. RL policy
2 0.6
8 0.5
-3
0.
0
Figure 8: Greedy and RL policies. A: greedy action policy given by Eq. (31) with and va in
(37) with P for the linear TSA problem with one-dimensional input. The r-axis shows values of the input, while p represents the student state expressed as w w" (1 p) w.p. B: best TD3 policy function found for this problem. Parameters: C' = 1, 0.02, a E [0, 11, w 1. w = -1
18

---

A. Linear regression
B. Sigmoidal perceptron
C. 2-layer NN
2.0
0.7
greedy Boo
gready 8
greedy Bso
1.5
0.5
best model
1.0
1.0
best model
best model
0.3
2
episodes
episades
episodes
gready
RL (best)
greedy
RL (best)
groedy
RL (hest)
1.5
1.5
1.5
0.5
0.5
-0.5
Figure 9: Convergence of RL agents. A, top panel: average steady-state running of the TD3 agent vs training episodes, for attacks on the linear regression model. Training episodes have length of 4 10 SGD steps, and policy updates are performed every 100 steps. The dotted line shows the average steady-state running cost of the greedy algorithm. The blue dot indicates the best performance achieved by the TD3 agent. Bottom panel: example of actions performed by the greedy attacker (dotted line) and by the best TD3 agent (blue line) on the same data stream. B, C: same quantities as shown A, for attacks on the sigmoidal perceptron and 2-layer NN. For the latter case. the TD3 agent observed the read-out weight layer only. The best TD3 agents were employed for the comparison shown in Fig. 3. Parameters: P C
10, n 0.02 D, E [-2,
A.
B.
1.0
1.0
0.5
r9 0.5
P-10
P-10
0.0
logıa(C)
Figure 10: Comparison of Adam and SGD dynamics. A: average relative distance vs training step for a logistic regression model classifying MNIST digits 1 and 7, under abbl-innerssio greedy attacks, for C 1. Solid and dashed lines correspond training via Adam and SGD, respectively. Average performed over 100 data streams. B: average steady-state relative distance as function of the cost of actions C and batch size P, obtained for the experiment described in panel A, and using the Adam optimizer. The orange shaded area shows the SGD-based theoretical estimate (Eq. (13)) for the range [1, 10). Averages performed over data streams of 10 batches, and over the last 1000 steps in each stream. Parameters: D 10, 7 0.1 (SGD), n 0.01 (Adam), E [0, 1].
19


Reviews:
[{"review_id": "c2AG7frKYs", "reviewer": "Reviewer_rUtu", "summary": "The paper provide an analysis of steady state of linear learners trained via SGD under online setting, where the found a phase transition in terms of attack strength. Some experiments are also conducted to demonstrate the insight from the theory.", "questions": "1. If the training algorithm is not SGD, instead it is, say Adam, how would this change the analysis result conceptually? In addition, in experiment would it change anything empirically?\n\n2. In Fig. 3, reinforcement learning and  clairvoyant methods are not compared for neural nets due to their complications. I can understand  clairvoyant might be infeasible due to high nonconvexity of the problem, but why RL methods are not feasible? It seems like the online adversarial attack could be a reinforcement learning problem by nature.", "limitations": "Limitation are sufficiently discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The formulation of attacking learning model under online setting is clean and intuitive. The theory is also illuminating. The insight that model performance will sharply decrease if attach strength is higher than a threshold is an interesting observation. In addition, the theory is supported by experiments.", "weaknesses": "Overall my feeling is both empirically and theoretically, the paper is not strong. Theory side, the main concern I have on the work is that the problem might be oversimplified, thus it is not sure how much the insight can carry over to more realistic settings. On empirical side, there are quite a few simplifications in the setting analyzed, e.g., linear model, SGD only training. While I agree theory should start simple, it would be more convincing to see experiments on more realistic settings, i.e., to test if the insights from the simple model can hold  for more practical settings, even if they do not hold, it would be still interesting to see the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive criticism and for the enthusiastic description of the strengths of our paper.\n\n**Weaknesses**\n\nOverall my feeling is both empirically and theoretically, the paper is not strong. Theory side, the main concern I have on the work is that the problem might be oversimplified, thus it is not sure how much the insight can carry over to more realistic settings. On empirical side, there are quite a few simplifications in the setting analyzed, e.g., linear model, SGD only training.\n\n* To the best of our knowledge, this is the first paper to study online poisoning from the theoretical point of view. We therefore decided to start with the simplest possible setting, linear models, which have been used to study various deep learning phenomena recently (feed-forward neural networks [1], self-supervised learning [2,3], pre-training [4], implicit bias[5-6] etc.) This framework allows us to obtain exact and explicit results, which are easy to interpret and help us develop our intuition about the problem.\n\nWhile I agree theory should start simple, it would be more convincing to see experiments on more realistic settings, i.e., to test if the insights from the simple model can hold for more practical settings, even if they do not hold, it would be still interesting to see the results.\n\n* We agree with the reviewer that it is key to verify that the insights obtained theoretically need to be verified experimentally in more realistic settings. We point the reviewer to the experiments with deep networks (LeNet, VGG, ResNet) on MNIST and CIFAR10 (Sec. 4), which confirmed the key insights from our theoretical analysis carried over to these settings, in particular the existence of a critical threshold of attack strength beyond which catastrophic collapse in accuracy happens.\n\n\n**Questions**\n\nIf the training algorithm is not SGD, instead it is, say Adam, how would this change the analysis result conceptually? In addition, in experiment would it change anything empirically?\n\n* Following the reviewer’s suggestion, we have run simulations for the case of logistic regression classifying MNIST data using Adam. The result is shown in the attached document - see Fig. A and B. The steady state reached by the learner is very similar to what we observe using SGD, thus providing further validation for our results. Due to the limited time allowed for the rebuttal, we could obtain the results for the logistic regression case only, and we will cover all real-data experiments considered in the draft for the final version of the paper. From a theoretical point of view, Adam has -- to the best of our knowledge -- defied an analysis even in the vanilla case so far (without attacks), with most recent work on learning dynamics focusing on vanilla SGD [6-9]\n\nIn Fig. 3, reinforcement learning and clairvoyant methods are not compared for neural nets due to their complications. I can understand clairvoyant might be infeasible due to high nonconvexity of the problem, but why RL methods are not feasible? It seems like the online adversarial attack could be a reinforcement learning problem by nature.\n\n* The clairvoyant setting is not doable due to the high non-convexity of the problem, as the reviewer points out. Running the clairvoyant non-linear solver becomes infeasible for complex architectures: finding a solution to the equations takes a long time, and since the problem is non-convex, there are no guarantees the sequence of actions converges to the optimal one.\n\n* In the RL approach, the state space is given by the input data and the learner’s weights. The latter makes an RL approach prohibitively expensive for large architectures, if you train all the weights. Following the reviewer’s question, we considered an approach where the whole network is trained, but our TD3 agent only attacks the network using knowledge of the read-out weights and the inputs. The results are shown in the attached document, see Fig. C and D. The agent is able to perform better than constant attacks, though, in terms of running cost, it does not get as close to the greedy attacks as it does when it has full sight of the learner’s parameters (for a comparison, see the paper Fig. 3-A,B bottom panels, and the supplementary material Fig. 5-A,B bottom panels). We will add these evaluations to the final version of the paper, and a note to clarify why exactly clairvoyant and RL-based approaches become not practical for complex models.\n\nWe hope that our answers have clarified the reviewer’s concerns and will provide grounds for a more favourable assessment of the paper; we would of course be happy to respond to further concerns during the discussion period.\n\nReferences\n\n[1] Saxe et al. ICLR ‘13;\n\n[2] Tian, Chen, Ganguli, ICML ‘21;\n\n[3] Jing, Vincent, LeCun, Tian, ICLR ‘22;\n\n[4] Wu, Zou, Braverman, Gu, Kakade, NeurIPS ‘22;\n\n[5] Moroshko, Woodworth, Gunasekar, Lee, Srebro, Soudry, NeurIPS ‘21; Li et al. NeurIPS ‘22;\n\n[6] Chizat & Bach NeurIPS ‘18;\n\n[7] Goldt et al. NeurIPS ‘19;\n\n[8] Ben Arous et al. JMLR ‘21;\n\n[9] Veiga et al. NeurIPS ‘22."}, {"review_id": "dTz2xkY4Cs", "reviewer": "Reviewer_cwDs", "summary": "The authors conduct theoretical analysis and empirical evaluation of poisoning attacks in the online learning setting, where the attacker can intervene in the labels of sequentially provided data. As a result of the theoretical analysis, the authors show that the strength of the attack becomes discontinuously stronger as the batch size asymptotically approaches infinity. It is also shown that even a greedy attack can be as strong as that in the clairvoyance setting under an appropriate condition.", "questions": "In equation 4, is a parameter to adjust the balance between g^per and g^nef necessary?\nIn equation 6, when d_mu(C,P)=1, it cannot be said that the student's prediction and the target's prediction coincide since they merely coincide in their expectations.", "limitations": "The subject is an attack on a learning system and it can affect society in a malicious way, but it is obvious that the research interest is in the theoretical aspect of the behavior of the system under attack.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "It introduces a new problem setup for poisoning, and although the analysis is performed in a very simple setting, it leads to interesting results.\nIt is interesting that a properly designed greedy attack is as effective as an attack in the clairvoyant setting.\nTheoretical analysis utilizing optimal control theory is not very common, and it is useful to introduce such methods.", "weaknesses": "There is little discussion of threat models and attacker models when viewed as a security issue. There is no disagreement that poisoning in an online setting is a serious threat, but the paper does not discuss where the significance of considering this type of dirty label attack lies and whether it could be a significant risk. In particular, I wonder if there is any point in dealing with a setting where the batch size is infinite in an online setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the constructive feedback. Please see below for our response.\n\n**Weaknesses**\n\nThere is little discussion of threat models and attacker models when viewed as a security issue. There is no disagreement that poisoning in an online setting is a serious threat, but the paper does not discuss where the significance of considering this type of dirty label attack lies and whether it could be a significant risk.\n\n* There are several practical use cases that motivate our analysis. In federated learning, where data are collected independently by each node in the federation, malicious nodes could modify the labels before providing the model updates to the central server for aggregation. Label attacks can also occur in online learning settings where models are fine-tuned on the fly using user-generated data, such as email spam filters, product recommendation engines, chatbots, and fake review detectors. Note that, in streaming scenarios, the attacker can monitor the effect of previous poisoning on the learner and make adaptive decisions on how to poison next. This adaptability, inherent to the online setting, makes attacks on online learners potentially extremely dangerous. We will expand the introductory section of the manuscript to include these examples.\n\nIn particular, I wonder if there is any point in dealing with a setting where the batch size is infinite in an online setting.\n\n* The Reviewer raises a good point: in practical contexts, it is unlikely that streaming data would arrive in batches of infinite size. We considered the case of infinitely large batches ($P\\to\\infty$) as an approximation for cases where $P$ is sufficiently large to make batch averages effectively equal to averages over the data distribution, which is a limit receiving much interest from the theoretical point of view recently [1-3]. This reduces the optimal control problem to a deterministic one, which we could solve exactly. We would like to point out that **our experiments approach the theoretical limit of $P\\to\\infty$ very rapidly**. See for example Fig. 2-B in the paper: for $P=10$, the steady state accuracy of the model already gets very close to the $P\\to\\infty$ prediction. Moreover, in practical applications, online learning may involve an accumulation phase where multiple batches are collected before being used to update the ML model, which represents a context where our analysis may apply.\n\n**Questions**\n\nIn equation 4, is a parameter to adjust the balance between g^per and g^nef necessary? \n\n* This parameter is necessary to ensure that the two costs have the same scale, so that we can analyse the effect that the attack strength has on the steady state of the learner in a standardised fashion across architectures. In more detail, the nefarious cost, $g^{\\mathrm{nef}}_{\\mu}$, represents the distance between the learner and the target at training step $\\mu$. This quantity can vary significantly depending on the setup of the experiment (the learner architecture, the target of the attacker, etc), thus affecting the amplitude of the perturbations. This makes it hard to compare results from different setups. In order to mitigate this effect, the perturbation cost, $g^{\\mathrm{per}}$, is weighted by a factor that has the same magnitude of the average nefarious cost. We hope this clarifies the role of  $\\mathcal{E}(\\phi^*)$, and we are happy to answer any further question the Reviewer may have.\n\nIn equation 6, when $d_{\\mu}(C,P)=1$, it cannot be said that the student's prediction and the target's prediction coincide since they merely coincide in their expectations.\n\n* We thank the reviewer for pointing this out. We will make the suggested correction to the sentence.\n\nWe hope that our answers have clarified the reviewer’s concerns and will provide grounds for a more favourable assessment of the paper; we would of course be happy to respond to further concerns during the discussion period.\n\nReferences\n\n[1] Ba et al. NeurIPS ‘22;\n\n[2] Damian et al. COLT ‘22;\n\n[3] Dandi et al. arXiv:2305.18270.\n"}, {"review_id": "bHTZx0Fpa2", "reviewer": "Reviewer_61gD", "summary": "This paper analyzes the robustness of online learners when the labels of the received data are manipulated. In particular, it analyzes a student-teacher online learning problem where the attacker poisons the labels provided by the teacher before feeding the student the labeled batch. The setup is analyzed both theoretically and experimentally where with the increase of the attack budget, the performance of the learner degrades significantly.", "questions": "In addition to the points raised in the weaknesses part, I have the following question:\\\n\n- To guarantee that the attack is imperceptible (in case of perturbing the input), the attacker has to produce the perturbations under budget constraints (e.g. $\\|\\delta\\|_\\infty \\leq \\frac{8}{255}$). How is this constraint translated to the proposed setup?\n\n- The perturbed label in Equation (1) could produce a real number for integer valued labels. Couldn't this be a simple check for the learner to reject such samples from training on them?", "limitations": "The authors have not addressed the limitations of this work such as the practicality of the proposed setup, the limited experimental setup (problem and dataset scale) along with how expensive is it to conduct such attacks.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The main strengths of this work are:\n\n(1) The paper is well-written and the figures are polished.\n\n(2) The setup is clearly explained and the theoretical analysis on synthetic data support the results.\n", "weaknesses": "There are few weaknesses that I hope to be addressed before getting this paper accepted:\n\n(1) The paper is missing a strong practical motivational example from real world scenarios when attackers have access to manipulate the *labels* before feeding the labeled batches to the learner. \n\n(2) While the proposed problem setup studies an online learning scheme, the attacker is allowed for an unbounded computational budget to manipulate the labels. However, in online learning, the environment can reveal new batches *irrespective* of how efficient the attacker is in manipulating the previously revealed batch. Note that this assumption (given unlimited computation to the attacker) is not realistic and it questions that effectiveness of the proposed attack.\n\n(3) Experimental evaluation are conducted on very small scale problems and datasets. I would expect evaluating the results on online learning datasets such as CLOC [A] and Firehose [B].\n\n(4) The analyzed attackers should be evaluated when a defense mechanism is presented. For instance, would a learner upon convergence still update all model parameters on each received data? What happens if the learner stored labeled examples from the stream before the poisoning phase starts and update on mixed batches?\n\n[A] Online Continual Learning with Natural Distribution Shifts: An Empirical Study with Visual Data, ICCV 2021.\n\n[B] Drinking from a Firehose: Continual Learning with Web-scale Natural Language, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the constructive criticism and the relevant questions. Please see below for our response.\n\n**Weaknesses**\n\nExamples of real world scenarios where attackers have access to manipulate the labels before feeding the labeled batches to the learner.\n\n* **There are several practical use cases where attackers have access to labels before the learner, motivating our analysis**. (i) In federated learning, where data are collected independently by each node in the federation. Malicious nodes could modify the labels before providing the model updates to the central server for aggregation. Even if data are distributed from the central server to the nodes, when collecting the model updates, the central server would have no access to the labels used locally to generate the updates. (ii) Label attacks can also occur in online learning settings where models are fine-tuned on the fly using user-generated data, such as email spam filters, product recommendation engines, chatbots, and fake review detectors. We will add these examples to the introductory section of the manuscript. Note that, in streaming scenarios, the attacker can monitor the effect of previous poisoning on the learner and make adaptive decisions on how to poison next. This adaptability, intrinsic to the online setting, makes attacks on online learners potentially extremely dangerous. \n\n\n...the attacker is allowed for an unbounded computational budget to manipulate the labels.\n\n* We agree with the reviewer that an unbounded computational budget for attacking the labels is unrealistic. Our proposed attack strategies have a small computational cost for deployment, however, as they only require one forward-and-backward pass on the learner architecture for the greedy attacks, and one forward pass on the TD3 agent for RL-based attacks. Moreover, we are considering attacks that target data labels, which have a reduced computational cost compared to high-dimensional adversarial perturbations of the inputs. These attacks might still be infeasible when data arrives with high frequency, so we will add a comment in the paper to reflect this limitation. To address this problem, we have extended our theoretical analysis to the case where the attacker poisons only a fraction $\\rho$ of each data batch (see answer to reviewer 7DCo). The result indicates that the attack strength effectively decreases by a factor $\\rho$. Our experiments support this finding (see Fig. E in the attached file).\n\n... evaluating the results on online learning datasets such as CLOC [A] and Firehose [B].\n\n* We agree with the reviewer that it would be interesting to explore attacks when clean data exhibits a natural covariate shift, as is the case in the CLOC and Firehose data sets, and we will explore this direction in future work. For this paper, our focus is on stationary distributions, and our theoretical analysis is based on this assumption. The goal of our experiments with deep architectures (LeNet, VGG, ResNet) on realistic datasets like MNIST and CIFAR10 was simply to verify our theoretical predictions in cases where data has non-trivial correlations and the optimisation problem is non-convex, which is standard practice in papers with a theory focus at venues like NeurIPS.\n\nWhat happens if the learner stored labeled examples from the stream before the poisoning phase starts and update on mixed batches?\n\n* We agree that it is important to design defence mechanisms against online adversarial attacks. However, the purpose of this paper was to establish the baseline behaviour of online learners when such attacks are present. This, to the best of our knowledge, was not known and it does already exhibit rich and interesting behaviours. Therefore, a thorough analysis of defence strategies would go beyond the scope of the present paper. \nA simple strategy that mixes (new) poisoned data with clean samples makes the problem equivalent to the case where only a fraction $\\rho$ of the data is perturbed by the attacker. Thus, our result mentioned above applies: the attack strength decreases by a factor $\\rho$. Note that, to implement this defence mechanism, simply storing data from before the attacks might be challenging - how does the victim know when the attacks start? It would instead be doable in the context of federated learning. \n\nHow is this constraint translated to the proposed setup?\n\n* The budget constraint is intrinsic in the setup of the optimal control problem as the attack strength (1/C), which effectively sets the amplitude of the attacks by affecting the perturbation cost. A large attack strength implies large perturbations. The question then is how small C must be to achieve a certain goal (for example making the accuracy low). Similarly, given a value of C, how close do different attack strategies get to a desired target? Our analysis addresses these questions.\n\n...a real number for integer valued labels. Couldn't this be a simple check for the learner to reject such samples from training on them?\n\n* A simple way to address this limitation is to discretise the actions. For example, greedy attacks could use the action $a^G_{\\mu}$ on average, replacing a fraction $\\rho=a^{\\mathrm{G}}_{\\mu}$ of the labels in each batch with $y^*$, and leaving the remaining clean labels unperturbed. \n\n**Limitations**\n\nIn the final version of the paper, we will expand the concluding section to include the limitations associated with the practicality of the proposed attacks (high frequency streams represent a challenge), and with the threat model (label attacks). We will also include the case of distributions with covariate shift and designing defence strategies as important directions for future work.\n\nWe hope our answers have clarified the reviewer’s concerns and will provide grounds for a more favorable assessment of the paper; we would be happy to respond to further concerns during the discussion period."}, {"review_id": "0XeLRVFcxR", "reviewer": "Reviewer_7DCo", "summary": "Data poisoning attacks have been extensively studied in the offline setting, while poisoning attacks in the online setting have received little attention. In the online setting, the attacker is forced to craft attacks exploiting the data stream, taking into account the state of the model and the possible future data stream to divert the model. This work aims to study theoretically and empirically the learning dynamics of an online learner subject to a poisoning attack in the white-box setting, i.e., the attacker knows the architecture and the current parameters of the target model. The problem of finding the best attack policy is formalized as a stochastic optimal control problem and is theoretically studied in the teacher-student setup. From that, the authors were able to obtain results about the steady state of an attacked linear regression model, i.e., the model weights, the optimal action and the distance of the target model depending on the cost of the attack, supposing both infinite and finite size batches. Furthermore, the work shows analytically that a greedy strategy can perform quite optimally. The experimental evaluation confirms the theoretical results on synthetic data and explores the dynamics of online data poisoning attacks on real data and non-linear predictors, showing that the theoretical findings almost hold in more complex scenarios.\n", "questions": "Major questions:\n\n- Why are the clairvoyant and RL attacks infeasible to deploy for complex models? Is it due to the time required for the calibration? This is not very clear from the text.\n\n- In Eq. 1, please clarify why it should be important to model an attacker that “under/overshoots”. Why can the attacker obtain a perturbed label that resides outside the interval between the clean and target labels?\n\n- I think that more details about the RL attack are needed. How is the problem of finding the optimal sequence of actions mapped to the RL problem? Which are the reasons for choosing to utilize TD3 (and a deep learning policy in general) instead of other RL approaches?\n\n- Which is the utility of gamma^tilde in the objective function minimized by the greedy attack? Is it used to address the fact that the attacker should not try the most effective attack at the subsequent time step, but she has to take into account all the future streams of instances? How does the calibration of gamma^tilde work? I invite the authors to add more details about this.\n\n- I suggest that the authors add a \"Take-home-messages/Discussion” section that summarizes the theoretical and empirical results and highlights how the results can be useful for designing a poisoning attack or defending against it. \n\n- The authors should clarify their threat model in the paper and where it may apply.\n\n\nMinor questions:\n\n - Are the results of Figures 1-B and 1-C obtained from the experimental evaluation? If yes, the setting used for obtaining these results should be indicated in the text. I may have missed it, so I kindly ask the authors to point me out the lines containing this information if it is included in the paper.\n\n- Should g^nef be at the place of one of the g^pre in eq. 16?\n\nEventually, I kindly ask the authors to fix the links to the equations that appear in the text, since they don’t work at the moment.\n", "limitations": "The authors have briefly discussed some limitations of their work in the conclusion section and they have clearly stated that extending their analysis to non-linear architectures and different probability distributions of the inputs is challenging. However, I think that a discussion about the limitations of the threat model considered is missing and I invite the authors to cover this point, by discussing, for example, why the attacker should only modify the labels of the instances. Moreover, I ask the authors to include a “take-on-messages/discussion” section to summarize and clarify the obtained results and their implications.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper makes a valuable contribution to the literature on data poisoning attacks, where there has been limited work in online settings. In particular:\n\n- The idea of analyzing the attacker’s control problem from the perspective of the teacher-student framework represents the strong main novelty of the paper, since the formulation of the attack problem as an optimal control problem has been discussed before. The analysis allows the authors to derive interesting results about the dynamics of the learning process of the model and the steady state of a linear regressor that have not previously been discussed in the literature. It is interesting to see that above a certain attack strength the accuracy of the attacked model may drop dramatically and perturbations above the threshold may not be sufficient to realize the attack.\n\n- The set of considered attack strategies sufficiently covers the possible options available to the attacker. The idea of showing that a greedy attack can be as effective as an attack with full knowledge is valuable. \n\n- The theoretical results are confirmed empirically and punctually. Moreover, the experimental results on non-linear architectures and real data suggest that the theoretical results may also hold for more complex scenarios, that’s an interesting finding.\n\n- The derivation of the theoretical results is explained in the appendix and the well-organized code to reproduce the experimental results is available (even though more instructions to reproduce the results may be added, like the Python version used by the authors to run the experiments).\n", "weaknesses": "- The theoretical analysis is limited to consider linear regression as the student model, the standard normal distribution as input distribution and an infinite time horizon, so the theoretical results are a bit limited. However, it is recognized by the authors that more general results are missing because deriving them in a more general scenario is hard. Furthermore, the authors tried to derive some intuitions about the results in a more complex scenario through the experimental evaluation. Covering the theoretical analysis in a more complex setting and with a finite time horizon is an interesting future work to explore.\n\n- It is not clearly motivated why the attacker can only modify the labels instead of the entire inputs and why the attacker should be able to apply the same perturbation to the entire batch (which turns out to be a very strong assumption). Data poisoning attackers should assume little control over the data to be considered practical [P1, P2].\n\n- The presentation of the theoretical results is a bit confusing since it is mixed with the presentation of part of the theoretical results.\n \n- The presentation of the attack strategies and their implementation lack details that cannot be found in the appendix. See the “Questions” section for more details.\n\n- From the paper, it is not evident what the take-home message is and what suggestions are provided to improve robustness in stream pipelines or make attackers more stealthy. The paper presents numerous useful analyses and extensive experimental settings but lacks a \"Take-home message/Discussion\" section that summarizes the overall findings and suggestions. While the authors have reported some of these in the conclusion section, I believe they can be further expanded with higher priority/attention.\n\n[P1] Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Federated Learning. In IEEE Symposium on Security and Privacy (2022). \n\n[P2] Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning. ACM Computing Surveys (2022).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the constructive criticism and the relevant questions. Please see below for our response.\n\n**Weaknesses**\n\nAttacker only modifies the labels instead of the entire inputs.\n\n* The case of online poisoning of the labels has not been addressed before, despite its relevance in several practical applications (federated learning, learning from user-generated data, etc), so our aim is to provide a first contribution to fill this gap. Note that attacks on the labels have a reduced computational cost compared to high-dimensional adversarial perturbations of the inputs, which makes label poisoning more convenient in a streaming scenario.\n\nPerturbation of the entire batch.\n\n* While the online setting requires the attacker to keep perturbing the data over time (as otherwise the perturbation may be forgotten by the learner), it is true that the attacker may be able to perturb only a fraction of samples in the batch. Our analytical derivation can be generalised to accommodate this scenario. In the linear TSA problem, we find that greedy attacks lead to an average steady-state distance given by ${(C P / (\\rho P + 2) + 1)}^{-1}$, with $\\rho$ the fraction of corrupted samples, which for $P$ large reduces to $(C/\\rho + 1)^-1$. This result indicates that the attack strength effectively decreases by a factor $\\rho$. Our experimental evaluations shown in Fig. E (attached file) support this finding. This result suggests that a simple defence mechanism consisting in mixing poisoned data with clean examples from a trusted source (in case this is available) could improve the model robustness.\n\nPresentation is a bit confusing.\n\n* We will highlight more our theoretical results in a separate, dedicated section in the final version of the paper. \n\nImplementation lacks details that cannot be found in the appendix.\n\n* We thank the reviewer for pointing this out. We will add an Appendix in the final version of the paper to include more details about our implementation and our experiments.\n\n**Questions**\n\nWhy Clairvoyant and RL attacks are infeasible?\n\n* The clairvoyant setting is not doable due to the high nonconvexity of the problem. For complex architectures, finding a solution to the equations takes too long to be practical. In the RL approach, the agent observes the state of the system, given by the input data and the learner’s weights, and produces an action according to its policy function. For big architectures, the state space is extremely large, and tuning the RL policy function becomes prohibitively expensive. \n\n* Following the Reviewer’s question, we considered using a TD3 agent that only observes the last-layer weights of the network, significantly reducing the dimension of the state space. The results are shown in Fig. C,D (attached document). The agent performs better than constant attacks, though it does not match the greedy attacks. We will add these evaluations to the final version of the paper.\n\nClarify why it should be important to model an attacker that “under/overshoots”.\n\n* There is in principle no reason why $a$ should be constrained within a bounded region, as the attacker’s optimization problem includes the perturbation cost proportional to $a^2$. It is up to the attacker, then, to find the best possible sequence of actions, accounting both for the perturbation and the nefarious costs. \n\nMore details about the RL attack are needed.\n\n* RL calibrates a policy function to maximise the expected total reward of the agent by interacting with the environment. In our case, the environment is characterised by the current learner’s weights and input data, with rewards given by the negative value of the running cost. A policy that maximises the expected rewards also minimises the running cost of the attacks, finding a solution to the attacker’s optimal control problem. We employed TD3 because it is a powerful agent that requires little tuning of the hyperparameters and can handle continuous action spaces.\n\nMore details about $\\tilde{\\gamma}$.\n\n* Calibrating $\\tilde{\\gamma}$ helps the greedy attacker overcoming the limitation of a strategy that only looks one step ahead, accounting for long-run effects of the actions. To calibrate $\\tilde{\\gamma}$, the attacker uses past observations to simulate data streams, and it evaluates the total cost of the simulated trajectory associated with different values of $\\tilde{\\gamma}$. Averaging over many data streams, the attacker finds the value of $\\tilde{\\gamma}$ that minimises the (simulated) total expected cost. \n\nThe authors should clarify their threat model.\n\n* We consider targeted attacks that aim for the ML model to learn a “nefarious” target function $\\phi^*$. The attacker perturbs the data labels to do so, so our setting can be considered a generalisation of label-flipping attacks. We consider attackers with different adversarial capabilities. In particular, RL agents ignore the learning rule and see part or all of the learner's architecture. Greedy attacks assume full knowledge of the learning rule and model parameters. \n\nMissing details of results of Figures 1-B and 1-C.\n\n* For those experiments, with considered streams of $10^4$ batches of size $P=1$, learning rate $\\eta=0.1$, and actions $a \\in [0, 1]$. We will add these details to the paper.\n\ng^nef at the place of one of the g^pre in eq. 16?\n\n* Yes. Typo fixed.\n\n**Limitations**\n\nWe thank the Reviewer for the insightful suggestions. We will expand the concluding section to include the limitations associated with the type of attacks (targeting the labels), and the threat model (white/black box attacks). We will as well include a take-home-message section summarising our results and clarifying their implications, incorporating Reviewers' feedback and including any valuable insight arising from the discussion period.\n\nWe hope that our answers have clarified the reviewer’s concerns and will provide grounds for a more favorable assessment of the paper."}, {"review_id": "K3itwPzolV", "reviewer": "Reviewer_MYtD", "summary": "This paper sheds light on the vulnerabilities of online learners to adversarial attacks and provides insights into the manipulation of learning dynamics. The findings highlight the need for robust defenses against such attacks and contribute to the growing body of research on data poisoning attacks in machine learning.\n", "questions": "1. How do different attack strategies compare in terms of efficacy?\n2. Are attacks subject to time constraints and do they involve transient dynamics? \n3. Does the analysis take into account temporal correlations within the data stream? \n4. The model's robustness improves or decreases of over-parametrization?\n", "limitations": "Missing limitation and negative societal impact discussion in this paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper provides a theoretical analysis of online data poisoning in the teacher-student setup, which is a popular framework for studying machine learning models in a controlled way. \n2. The paper compares different attack strategies and finds that properly calibrated greedy attacks can be as effective as attacks with full knowledge of the incoming data stream. \n3. The authors empirically study online data poisoning on real datasets, such as MNIST and CIFAR10, using various architectures like LeNet, ResNet, and VGG. \n", "weaknesses": "1. This paper primarily focuses on linear regression models and does not extensively explore the impact of adversarial attacks on other types of machine learning models.\n2. This paper does not provide specific examples of real-world scenarios where adversarial attacks on online learners can have significant consequences. \n3. This paper lacks extensively discuss potential defense mechanisms or countermeasures to mitigate the impact of these attacks. \n4. This paper does not thoroughly compare its findings with existing literature on attacks on online learners. \n5. The practicality studied threat model should be discussed with more details. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the constructive criticism and the relevant questions. Please see below for our response.\n\n**Weaknesses**\n\nThis paper primarily focuses on linear regression models and does not extensively explore the impact of adversarial attacks on other types of machine learning models.\n\n* The problem of online adversarial attacks has not been addressed theoretically before, so decided to start with the simplest possible setting: linear models. This allowed us to obtain exact and explicit results, which can help develop intuitions about the problem. Note that various deep learning phenomena have been investigated by means of linear models recently (feed-forward neural networks [1], self-supervised learning [2,3], pre-training [4], implicit bias[5-6]).\nWe agree with the reviewer that it is crucial to verify if the insights obtained theoretically carry over to more realistic settings. For this reason, we extensively performed experiments with deep networks (LeNet, VGG, ResNet) on MNIST and CIFAR10. We found that key insights from our theoretical analysis, e.g. the steady-state behavior of the learner under attack, are replicated in these settings.\nAdditionally, we have now expanded our empirical evaluations using Adam (see Fig. A, B in the attached document), thus exploring even further more realistic use-cases.\n\nExamples of real-world scenarios.\n\n* Several practical use cases motivate our analysis. In federated learning, for example, malicious nodes in the federation can modify the labels before sending the model updates to the central server for aggregation. Label attacks can also occur in online learning settings where models are fine-tuned on the fly using user-generated data, such as email spam filters, product recommendation engines, chatbots, and fake review detectors. The online setting makes adversarial attacks extremely dangerous, since the attackers can monitor the effect of previous poisoning on the learner and make adaptive decisions on how to poison next. \n\nDefense mechanisms.\n\n* Our contribution aims to establish the fundamental behavior of online learners under attack. This problem has not been addressed before theoretically, and the analysed baseline already exhibits rich and non-trivial phenomena. Therefore, a comprehensive analysis of defence strategies would extend beyond the scope of the current paper. Nevertheless, we note that our analysis of attacks that only perturb a fraction $\\rho$ of the data (see answer to reviewer 7DCo) is suitable for describing a defence strategy combining the poisoned data with a trusted source of clean data. We found that the attack strength decreases by a factor $\\rho$ in this case.\n\nCompare findings with existing literature.\n\n* We did an extensive search for studies addressing the problem of online label poisoning but could not find any relevant paper for benchmarking our methods. We will be happy to consider any additional reference in case the Reviewer had specific suggestions.\n\nThe practicality studied threat model should be discussed with more details.\n\n* We consider targeted attacks that aim for the ML model to learn a “nefarious” target function $\\phi^*$. The attacker perturbs the data labels to do so, so our setting can be considered a generalisation of label-flipping attacks. We consider attackers with different adversarial capabilities. RL agents ignore the learning algorithm used for training the ML model and see the model architecture. Greedy attacks assume full knowledge of the learning rule and model parameters.\n\n**Questions**\n\nHow do different attack strategies compare in terms of efficacy?\n\n* We compared the efficacy of different attack strategies in terms of the average running costs achieved at steady state (see Eq. (16) in the paper). The results are shown in Fig. 3 (paper, main text). Our evaluations indicate that clairvoyant (CV) attacks are the most efficient. This is expected as CV attacks have the advantage of seeing the future data stream upfront. Remarkably, greedy attacks almost match the clairvoyant efficiency in all settings that we considered. RL attacks perform well too when the agent can observe the entire state of the system, and become less effective otherwise (Fig. C, attached document).\n\n\nTransient dynamics and temporal correlations.\n\n* These are indeed interesting scenarios to be explored. They however need a significantly different setup compared to our analysis, where a key assumption is that the attacker tries to minimise the expected cost at steady state. Nevertheless, we shall note that our optimal control formulation can be re-cast in a finite-horizon scenario, which would be suitable to study time-constrained attacks and data exhibiting correlations in time. We have a comment in the concluding section of the paper that include the above considerations.\n\nRobustness improves or decreases with over-parametrization?\n\n* Our real-data experiments suggest that the robustness of ML models may decrease for highly parametrised architectures compared to simple ones (see the results obtained for a logistic regression and LeNet on the same dataset, Fig. 4-A in the paper). A thorough analysis of the role of over-parametrization represents yet another interesting research direction that could be addressed in a dedicated study. \n\n**Limitations**\n\n* In the concluding section, we present several limitations of our analysis, including the assumption of stationary data, the infinite-horizon setup, and the unexplored role of model complexity. In the final version of the paper, we will expand this section to include the limitations associated with the type of attacks (targeting the labels), and the threat model (white/black box attacks). \n\nReferences\n\n[1] Saxe et al. ICLR ‘13;\n\n[2] Tian, Chen, Ganguli, ICML ‘21;\n\n[3] Jing, Vincent, LeCun, Tian, ICLR ‘22;\n\n[4]  Wu, Zou, Braverman, Gu, Kakade, NeurIPS ‘22;\n\n[5] Moroshko, Woodworth, Gunasekar, Lee, Srebro, Soudry, NeurIPS ‘21; \n\n[6] Li et al. NeurIPS ‘22.\n"}]

Author rebuttal:
We would like to thank the reviewers for their constructive criticism. We are thrilled to see that the reviewers broadly agree this is an important, underexplored problem, and that our theoretical and empirical analysis offers some novel, non-trivial insights. We certainly agree that the scenario we study analytically is simplified, but we would like to point out that obtaining analytical results on learning dynamics is non-trivial even with simplified models, and the insights we derive are replicated in our analysis of deep networks (VGG, ResNet) on realistic data sets (MNIST, CIFAR10).

Concretely, the reviewers pose several interesting questions (detailed inline response below); while several such questions would necessitate a significantly broader scope than afforded by this paper, we have implemented a number of suggestions, namely:

* We have analysed empirically the dynamics of attacks when the learning algorithm employed is Adam, instead of vanilla SGD, observing again a very good agreement with our theoretical insights, see Fig. A, B (suggested by reviewer rUtu).

* We extended the reinforcement learning analysis to more complex models, under the proviso of using only the last layer weights to characterise the state of the student (unavoidable due to the very large state space resulting for using the full weight set of a DNN), with results in line with what we observed on simpler models, see Fig. C, D (addressing the questions of reviewers rUtu and 7DCo)

* We have examined analytically a simple defense mechanism/alternative scenario where only a fraction $\rho$ of labels are perturbed in each batch (as requested by reviewers 61gD and 7DCo). This can still be analysed theoretically in simple cases and reveals that the attack strength effectively decreases by a factor $\rho$.

* We will significantly expand our discussion of practical use-cases where our type of attacks can arise, namely the fine-tuning of systems learning from user-generated data and federated learning (suggested by reviewers cwDs, 61gD, and MYtD)

We hope that these extra analyses, and the detailed replies we give below, will be useful in informing a constructive discussion period, solidifying the positive outlook on the general work, and highlighting the necessity of some of the restrictive assumptions we make.


Meta-review: This work studies the robustness of online learners to attackers that can perturb the data, specifically the labels, in order to inflict higher loss on the learner. The theoretical and empirical content of the submission consider the amount of data needed by the attacker, different strengths of attack, and different types of learner (from linear to small but real deep networks like ResNet-18). Five expert reviewers with backgrounds in adversarial training, attacks and poisoning, and continual learning are initially split between acceptance (cwDs: 6, 7DCo: 5, MYtD: 5) and rejection (61gD: 3, rUtu: 4). The authors provide a rebuttal, most reviewers (except MYtD, rUtu) engage in author-reviewer discussion, and rUtu engaged in AC-reviewer discussion. rUtu ultimately raised switch to accept (rating: 6) given the rebuttal and the results for different optimizers (SGD, Adam) and deep albeit toy architectures (LeNet, ResNet-18). Following all discussion, 4/5 reviewers side with acceptance save for the notable exception of 61gD, who objects to the problem statement (the threat model gives the attacker a lot of power in the streaming setting) and scope of the work (no "true" online problems like continual learning or dataset shift) as too limited. The AC sides with acceptance in agreement with the majority of reviewers: this work is theoretically and empirically informative, and the experiments are more practical than some more theoretical work that only addresses linear models, and publishing this work can guide more research on the topic.

To unpack the negatives in more detail: the argument for rejection is that the chosen setting is unrealistic and unmotivated (in a streaming setting, the attacker might not have access to labels, and the attacker may not have unbounded computation time because the environment/others might keep providing a stream of inputs to the learner). Discussion does not persuade 61gD, who requests the study of "true" online problems like continual learning or distribution shift instead of streaming stationary problems (like MNIST or CIFAR-10 classification). Furthermore, they want to see analysis and results with at least some form of defense. The AC agrees that these are all directions for progress in future work (and thanks 61Gd for the detailed and grounded review with references), but nevertheless sides with acceptance, so that this paper can contribute its findings for online learning and encourage more work in this area. This is especially true with the inclusion of the rebuttal material.

The AC encourages the authors to incorporate the feedback from reviews and in particular to discuss the limitations emphasized by 61gD. Clearly identifying the scope of what has been done and remains to be done is a service to the reader and can result in more impact rather than less.

Note: the AC acknowledges the comment from the authors regarding the initial lack of reviewer engagement. The AC pursued post-rebuttal discussion, resulting in eventual engagement by all but one reviewer, and considered each review-rebuttal point independently for the cases when the reviewer did not respond.
Decision: Accept (poster)