Online false discovery rate control for anomaly detection in time series
Authors: Quentin Rebjock
Baris Kurt
Tim Januschowski
Laurent Callot
Venue: NeurIPS 2021 Poster (2021)
Keywords: false discovery rate control
anomaly detection
time series
statistical machine learning

Abstract: This article proposes novel rules for false discovery rate control (FDRC) geared towards online anomaly detection in time series. Online FDRC rules allow to control the properties of a sequence of statistical tests. In the context of anomaly detection, the null hypothesis is that an observation is normal and the alternative is that it is anomalous. FDRC rules allow users to target a lower bound on precision in unsupervised settings. The methods proposed in this article overcome short-comings of previous FDRC rules in the context of anomaly detection, in particular ensuring that power remains high even when the alternative is exceedingly rare (typical in anomaly detection) and the test statistics are serially dependent (typical in time series). We show the soundness of these rules in both theory and experiments.

Online false discovery rate control for anomaly detection in time series
Quentin Rebjock" EPFL
Barıs Kurt Amazon Research
Tim Januschowski Amazon Research
Laurent Callot Amazon Research
Abstract
This article proposes novel rules for false discovery rate control (FDRC) geared towards online anomaly detection in time series. Online FDRC rules allow control the properties of a sequence of statistical tests. In the context of anomaly detection, the null hypothesis is that observation is normal and the alterna- tive is that it is anomalous. FDRC rules allow users to target lower bound on precision in unsupervised settings. The methods proposed in this article overcome short-comings of previous FDRC rules in the context of anomaly detection, in par- ticular ensuring that power remains high even when the alternative exceedingly rare (typical in anomaly detection) and the test statistics are serially dependent (typical in time series). We show the soundness of these rules in both theory and experiments.
Introduction
Online anomaly detection is critical for many monitoring applications in health care, IT operations, manufacturing, or retail (e.g., [1] 4 20).. In such settings, observations one or several metrics of interest (naturally represented time series)
sequentially to detector. It is tasked with deciding whether a given observation is anomalous or not. Accordingly, anomaly detection time- series data is rich field that has been surveyed in several articles 6 Foorthuis
[ proposes typology of anomalies, and Sadik and Gruenwald 21 discusses open research questions in the field.
Arguably one of the most common approaches in addressing anomaly detection is via employing an unsupervised probabilistic anomaly scorer that assigns a probability to each point. This translates the problem of anomaly detection into of online multiple hypotheses testing. Specifically, at each time step t, we observe a new data point 2, and emit the null hypothesis H; that 2 is not anomalous. This hypothesis is tested with p-value provided by the scorer and may be rejected (detection an anomaly) there enough evidence against it.
As in any statistical testing problem, decision threshold determines whether the null hypothesis is rejected or not. In the case single test, most common convention is report a discovery (a point is anomalous) if the associated p-value is smaller than some preselected threshold a. The effect said to be statistically significunt level and the probability to falsely declare the point anomalous is less than a. Importantly, in the case of multiple hypotheses tests, the threshold does not provide similar guarantees and the fraction false positives may be arbitrarily close to 1. This particularly applies to anomaly detection because the proportion of alternative hypotheses tends to be very low. Hence, multiple hypotheses testing requires other mechanisms to set decision thresholds. In the case where all p- values are known in advance (offline setting), classical methods typically shrink the threshold a conservatively 2 27
In the setting of anomaly detection, natural quantity to control is the false discovery rate (FDR) as introduced by 2 that is, the ratio of falsely labeled anomalies to total anomalies. Methods for
*Correspondence: quentin. reentin.reejoocdepf...
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

sequential FDR control (FDRC) were pioneered by [10] who proposed the so-called a-investing strategy, which was later built upon and generalized methods are appealing for anomaly detection problems as controlling the false discovery rate is equivalent to maximizing recall given a lower bound on precision. Consequently this allows to trade-off precision and recall even in the absence of labelled data, which is another commonality of anomaly detection. All online FDRC methods allocate some threshold at every time step, and reject the hypothesis based on it.
5 [6] Online FDRC
The main contribution of this article is the proposal of a novel method to overeome a common limitation of existing online FDRC methods that renders them unsuited for online anomaly detection tasks. When few rejections are made because the alternative hypothesis is extremely rare, as the case in most anomaly detection problems. rejection thresholds of existing methods tend to zero. This phenomenon referred to as a--eath in the literature [88] and prevents any future discoveries causing a loss of power. To circumvent this problem, we propose a method based on memory decay, revisiting [8]. to ensure that rejection thresholds are lower-bounded by a non-zero value. This guarantees that we have power even in the case where alternatives (anomalies) are rare. We demonstrate that this method allows us to control the decaying memory FDR [ a version of the FDR metric adapted to infinite streams that progressively forgets past decisions. Our approach is fully general in the sense that it can enhance all of the most popular algorithms in the generalized a-investing class.
Our second contribution is the adaptation of the local dependency framework E5 to memory decay. This allows to use our methods for practical applications where p-values are in general not indepen- dent. We evaluate experimentally the performances of the proposed algorithms and demonstrate that we can overcome the challenges occurring when alternative hypotheses are exceedingly rare.
This paper is structured as follows. Section formalizes the problem of multiple hypotheses testing for anomaly detection and defines the false discovery rate. Section reviews the main methods for online FDRC and illustrates their limitations. Section SestionFdeetee details our contributions to prevent a-death. Section 5 proposses an adjustment to make the algorithms robust to local dependency in the p-values. Finally, Section O shows experimentally that our method preserves power while controlling the false discovery rate in anomaly detection settings. We conclude in Section /
2 Problem Formalization: Multiple hypotheses testing for anomaly detection
We formalize the problem statement of online anomaly detection via an unsupervised approach using probabilistic time series models. There is a rich and growing literature describing such probabilistic well suited for anomaly detection.
models (e.g.,
5 4
26 2
R
Deriving p-values. At each time step hypothesis He is tested based a p-value that must be obtained from past observations only. The concept of anomaly is ambiguous and suffers from a subjective and imprecise definition (9]. We assume that anomalies are characterized by statistically rare events that deviate significantly from expectations. For this reason, it is natural to address anomaly detection through probabilistic forecasting. A probabilistic forecast is an estimation of the probability distribution of 2 given the past, that is Prob(z, ,e, < l). or equivalently its c.d.f. Fj. Under the null hypothesis (no anomaly), such a forecast should be a decent estimate of 2t. From the forecast we can derive p-value Pt. which is the probability to observe an event in the tail of the distribution relative to 2, under the assumption that H, null. Hence, small value for pt is an indication that H, must be rejected. We may derive two-sided p-values as pt 2 min (F) - (zx)) using the predicted c.d.f. F, for symmetric distributions.
With this principle, we can infer a sequence of p-values {p: iteratively as new observations are made available. Instead of two-sided p-values, other scenarios are conceivable as for certain usages, it may make sense to define anomalies as values either extremely high or low compared to the median. For example, in a scenario where we monitor the resources usage of a compute service, only large values should result in an alert. Accordingly, one-sided p-values can be derived to account for only one end of the distribution. More generally, p-values need only to be stochastically larger than the uniform distribution under the null hypothesis, that is:
if H, is truly null then Prob(p: S u) < u for all u E [0,1]]
(I)
2

---

With this definition of anomalies, we can decompose the problem of anomaly detection into two distinct sub-puu cub--roblems: (i) obtaining p-values in line with the application via forecasting model and (ii) using criterion on the p-values to accept/reject hypotheses. We will assume time series models to be given and focus on (ii), that is, the choice of decision thresholds.
False discovery rate control. As we reject hypotheses we want to make sure that we do not falsely report too many anomalies. If there was a single hypothesis we could reject it if the associated p-value is smaller than some threshold a: this ensures that the probability to report when is not less than a. This is an immediate consequence of the definition of the p-value in Equation ①T. However, this procedure does not provide similar guarantees for set of hypotheses in general and for sequentially dependent p-values as in the case of online anomaly detection in time series in particular. For this reason, in multiple hypotheses settings rejections are based on procedures controlling metrics pertaining to set of tests.
anomaly
One of these metrics is the family-wise error rate (FWER) 13 which is the probability to make least one false discovery. The probability reject a truly null hypothesis approaches when the number of tests grows. This makes the FWER metric too conservative, leading to very few discoveries for long (possibly infinite) streams of data.
The false discovery rate (FDR) is the more natural quantity to control in our setting. Procedures controlling the FDR aim at maximizing the number of true discoveries subject upper bound on the expected proportion of false discoveries. This is equivalent to maximizing recall subject to user-defined lower bound on precision. For given set of hypotheses the FDR is formally defined as the expected ratio of false positives to total discoveries:
[ [R]
n R
FDR A
E [FDP] -
E
V
where 7t and R are the sets of truly null hypotheses and rejections respectively, and FDP is the false discovery proportion of the samples.
This article is concerned with the problem of online FDR control where observations arrive se- quentially and we want to make decision immediately whether to classify the observation as anomalous or not. Alternative settings have been investigated in the literature. Rather than making decision every time step. Zmic al. 33 considers testing sequences of hypotheses by batches of variable length. This takes advantage of a partial ordering of the p-values at the cost of a delay in the decision, which is not desirable in online anomaly detection. Another option is to aggregate and perform FDR control consequently, either sequentially or based on forecasts. Wang BI propose to perform online anomaly detection by coupling a STL decomposition with a FDR method based on the distribution of statistics or the residuals building on a method proposed by Sun and Cai 129
a series of p-values 17 12 multivariate
3 Background: Online FDR control
Online testing algorithms aim at controlling a time-dependent variant of the FDR that we define as follows. We R, denote the rejection indicator at time and define the number of rejections R(T) and of the number of false positives V (TT) up to time T as
T Σ R,1st e H.)
R(T)
R and V(T)
Naturally, we define the FDP and FDR at time T as FDP(T) respectively.
VIT) RRTVI and FDR(T) = E [FDP(T)]
Online decision rules that control the FDR allocate decision threshold aa to test hypothesis He at every time step f. The hypothesis is rejected if the associated p-value is less than a₁ and the rejection indicator is R₁ = 1(p S az). We wish to pick the rejection thresholds {ar) in such a way that FDR(T) I a at any time T for some FDR target E [0. Decision thresholds must depend solely on past observations, so that for any time there is function fe such that
a₁ fi ... R.-1) 1
(2)
3

---

of decision rules relying oracle where F o R.) is the o-field (information known) at time t. In this section, we make the standard conditional super-uniformity assumption that
if H, is truly null then Prob(p: Su | S u for all u E [0,
(3)
which is satisfied if frr is sequence of valid p-values and if null p-values are independent of all others. The independence assumption can be questionable for time series data in certain settings. We propose a method to relax it in Section 1o but we maintain it until then to simplify the exposition.
Generalized a-investing. The first algorithm controlling (a modified version of) the FDR was introduced by [C with the idea of a-investing. This algorithm is part of a broader class of al- gorithms known as generalized a-investing (GAI) rules [.. Algorithms of the GAI class record quantity wa called the wealth, that represents the allocation potential for future decision thresholds. They start with an initial wealth wo E (0, a) and at every time step t, an amount o, is spent from the remaining wealth order to test the hypothesis H, at level oạ- When a rejection occurs, an amount of thz is earned back, which induces the update wi W th. + Ry The wealth must always be non-negative, which imposes d I W;-1, and the (modified) FDR controlled only the quantities the are bounded adequately. The exact FDR can be controlled by algorithms called LORD and LOND [5]. These algorithms are part of the GAI framework, and satisfy a monotonic property, meaning that fa is coordinate-wise non-decreasing function in Equation (2) In fact, any monotonic GAI rule controls the FDR, under the assumption that p-values are independent []6.
Oracle rules. Monotonic GAI rules can be seen special case estimates of the FDP
18
19
30
Maintaining the quantity
EIST.EEH FDP* = R(T)
below a at time T guarantees that FDR(T) S a. This oracle cannot be evaluated as the set of null hypotheses HD is not known. A simple way to upper-bound FDP" is to remove the condition
i E HD in the summation, which leads to class of algorithms known as LORD 15 16
18
More
refined upper-bounds give rise to adaptive algorithms known as SAFFRON and ADDIS 19 30 In
short, LORD can be seen as an online version the Benjaaini-Hochherg procedure 22. SAFFRON online version of (27], and ADDIS is able to slightly improve SAFFRON's performances when null p-values are not exactly uniformly distributed, but stochastically larger than uniform. The algorithms SAFFRON and ADDIS are able to improve slightly LORD'S 's power when the proportion of alternative hypotheses is large, typically more than 50%, which is not the case in anomaly detec- tion. We illustrate this in Figure T For this reason we focus on LORD and provide more detailed discussion about SAFFRON and ADDIS in Appendix
The oracle estimate of LORD is given by
EiST On FDPLORD (T) R(T) V1
and offers lot of flexibility. FDR control at time 7 holds for any sequence {a chosen such that FTP(T) < a, provided that the functions fs (in Equation [ are coordinate-wist non-decreasing. We show here how to generate such sequence as suggested in [8 We let {nd]2 denote a non- increasing sequence summing to 1, where we set % 0 for all S 0 for convenience. We also let Pj min(t 2 0 E Rd 2 j} denote the time of the jth rejection (and oo if it doesn't 't exist).
Then the sequence defined by
at wo(Te 7t-ps) + a Σ TT-p
j21
satisfies the FDR control requirements. Note that thresholds decrease to zero except when new rejections are made.
Using the same notations, a special instance of ADDIS is given by the sequence
ar (r- (1)))w00(7s000) 75,(0) + Σ 73,00) A X,
(5)

---

for some fixed parameters > > À > O, and where we define
Sy(t) 1[t p,} P
Σ
H
The corresponding SAFFRON algorithm is recovered by setting = 1.
Limitations FDR rules. Anomalies are by definition rare events and the proportion alterna- tive hypotheses in the stream is expected to be very low, typically less than 1% in practice. This induces two distinct problems for the discovery of anomalies:
P.1 The lower the proportion of alternatives, the harder it to distinguish them from nulls with extreme values. This difficulty is inherent to FDR control, be it offline online, and makes anomaly detection challenging.
P.2 In the online setting, the decision thresholds ar decreases monotonously while no rejection is made. Hence, if no rejection is made for long time, the thresholds will be essentially null and no additional discovery will occur. This phenomenon is known as a-death and causes a loss of power in anomaly detection regimes.
The power of these algorithms depends on {+ and on the nature of the data since they are general and make minimal assumptions. In the remaining, use the default and robust sequences derived by 18
19 30
log(tA2) for LORD. In experiments involving SAFFRON that is, 7/ texp texp /log(t)
and ADDIS we also use standard parameters; see Appendix for more details. Figure U illustrates
10
rejections
SAFFRON
0.8
10 3
power
10
0.6
10-5
0.4
10-6
10-2
10-1 proportion alternatives T
10a
1000
2000
3000
4000
5000
Figure 1: Illustration of the difficulties encountered in FDR control for anomaly detection. (Left)
The power decreases to zero when the proportion of alternative hypotheses कi low for FDR controllers. Stream of artificially generated p-values from observations either from (0, 1) (null) or (3,, 1) (anomaly) with proportion Ti. (Right) SAFFRON's 's decision thresholds ar as a function of time for target 0.1 and the canonical sequence {
both of these problems. In the regime where the proportion of alternatives is low, LORD, SAFFRON and ADDIS all exhibit the same (poor) performances. Selecting sequence { going zero as slowly as possible helps to overcome P.2 to some extent but worsens P.I in contrast.
4 Cireumventing o-death
In this section, we tackle issue of a-death described Section g which the biggest practical problem of FDR control for anomaly detection. This suggests change in the FDR metric, as indicated by [8]. They introduced a decaying memory version of the FDR, meaning that the past forgotten with discount factor 1].
5

---

Memory decay FDR. count (T)
We define decaying memory rejections count (T) and false positives
I (T(T) = Σ 8 and Vi(T) Σ 8 RR
T
In words, more weight is given recent rejections, and the past shrinks exponentially. This is guably the most intuitive notion of FDR for very long, possibly infinite streams of data. Consistently, the decaying memory FDR at level ö defined as
(T (T) v1
FDRg(T) E (T)
(6)
The LORD rejection thresholds can be adapted
04 = wp ( min(ps.)) ph p1) + 5 Pt-Pstt 7t-
(7)
J21
in order to control the memory FDR at the desired level as proposed by 18 They also show that
inhibits a phenomenon known as piggybacking [8]. where threshold increments accumulated by previous rejections lead to sequence of bad decisions.
However, after the first rejection, decision thresholds in Equation ? suffer from an exponential decay and quickly tend to zero if no rejection is done in the next few steps. The authors suggest that when thresholds are too low, the rejection process should be paused and abstain from making any decision. After some time the oracle estimate decreases because of the exponential decay and the rejection process can be resumed. This scheme poses two problems: (i) during an abstention phase are not able to reject any hypothesis, even those with very low p-values that might be critical and (ii) there is no theoretical guarantee that the FDR still controlled after resetting the process with initial values.
In this section we establish one the key contributions of this paper, showing that the idea of mem- ory decay, allows to avoid a-death while controlling the FDR. When no rejection is made both (I") and (T') decay zero. Intuitively, this translates into a minimal rejection threshold that doesn't I depend on the last rejection time. The standard expression of the FDR contains an asymme- try before and after the first rejection time Pi because the operator in the denominator, For this reason, our results are more naturally expressed in terms of smoothed FDR (inspired from (16)., that
VT( AFDR,(T) E (sFDP = (T) +
for some small smoothing parameter 77 > O. We show in Appendix D how deal with the case where the quantity to control is the memory FDR at level as defined in Equation G
LORD memory decay. As Section that decision thresholds ar = f R.-1) are functions of the past. We define the memory decay version of the LORD oracle
we express algorithms in terms of oracle rules. Remember
FDP LORD (T) EiST 8
R3(T) +
We derive a memory decay analogue of the results
18
Proposition 1. Suppose that functions ft are coordinatewise non-decreasing. If p-values satisfy relation then picking decision thresholds ar such that FDP FDPLORD (T') a time T ensures that sFDR, S a.
Proof given Appendix
As for all oracle rules presented above, Proposition gives a lot of freedom regarding the choice of the sequence of decision thresholds. We exhibit here special instance that naturally generalizes the standard LORD algorithm and that doesn't 't suffer from o-death when < 1. Let )o be
positive non-increasing sequence such that ET 5 -T < 1 for all T. Notice that such sequence

---

admits limit no larger than - 8, and may be chosen lower-bounded by 1 - 6. A natural choice is y. max(Ni, 6). Rejection thresholds defined as
cnri: + Σ 8 01 7t-ps
(8)
satisfy the assumptions of Proposition In the case where 7 max(":, 1 6), this means that there is minimal rejection threshold, namely any(1 - 5). no matter how long ago the last rejection occurred.
SAFFRON and ADDIS memory decay. Algorithms SAFFRON 19 and ADDIS 30 can be adapted in the same way as LORD order to avoid a-death. We defer precise statements and analysis to
Appendix B We provide here special instance for some fixed parameters 1 X > 0. The
sequence thresholds defined by
0r a(T 2) (1 + EsT-ss))) AA
(9)
controls the smoothed memory decaying FDR level a. Here again, in the case where % max 1 8), this means that there is a minimal rejection threshold, namely a ()(1-8)) A. In Figure we exhibit a qualitative example showing how the minimal rejection threshold helps to
Tima Slapp
Deeap SAPPRON
Time Stogs
Figure 2: SAFFRON rejection threshold with memory decay (bottom) and without (top). True posi- tives green, false positives red, false negatives in purple. Without memory decay, the rejection threshold decreases much that further discoveries are impossible.
make discoveries after long time without anomalies.
5 Local dependency
In this section, we show how to theoretically overcome the limitation posed by the independence of p-values implied by the super-uniformity assumption B Time series data contains dependencies that may leak to the p-values. If null p-values depend on each other the super-uniformity assumption may be broken. We propose a method deal with the case where null p-values are allowed to be locally dependent.
Thresholds of the LOND and LORD algorithms can be adapted to control FDR under arbitrary depen- dence of p-values 15 [6] in analogy to the Benjamini-Yckutieli procedure B in the offline setting.
It consists essentially in dividing thresholds by the quantity q(T) A Σ'= at all steps. By ex- tension, SAFFRON and ADDIS could be corrected similar way. However, this calibration makes thresholds essentially null in the long term q(T') goes to infinity. The reason is that arbitrary

---

dependency of p-values is an overly restrictive supposition. As shown in Section 2 the most natural way derive p-values is to generate probabilistic forecast. At time step such a forecast is typically based on context, that is, sequence of past observations of finite length. If the dependence in the data is controlled by the forecasting model then the p-value Pt is independent on remote p- p-values. More specifically, depends on the last L, p- p-values only, or, in other words,
Pt 1 Pr. Pt-L-11
(10)
provided that L, large enough. Most commonly, the dependency range is constant over time, that is, L, = L for all f. which we are going to assume. Notice that L = 0 and L = oC recover the independence and arbitrary dependence settings respectively.
The asynchronous hypotheses testing framework established by 64 proposes an approach to con-
trol modified definition of FDR under local dependency of p-values. We show how to adapt the memory decay LORD algorithm for local dependency in order to control
E[V)
mFDR(7)
E (T)] +
We define the memory decay LORD oracle for locally dependent p-values
E1ST 8" 0 Rg(T) +
FDP dep (T)
Proposition Suppose that decision thresholds are monotone with respect to rejection indicators. If p-values are locally dependent, that is, satisfy relation (TO) then picking decision thresholds such that FDP 5
dep (T) S ensures that mFDR(T) S at any time T.
Proof given Appendix
As special instance of this algorithm we can define
anr + Σ --
Notice that increases of the thresholds coming from rejections are delayed by the context length L.. This procedure controls only a modified version of the FDR but is known that mFDR behaves like FDR when the number of time steps is large (T))
6 Experiments
6.1 Simulations
In this section aim documenting that our proposed methods are indeed able control the decay FDR when the proportion of alternative hypothesis (anomalies) decreases while maintaining power. This article does not aim at asserting whether FDRC method can yield higher accuracy than alternative threshold selection methods, such as fixed threshold, for anomaly detection tasks. The main advantage of FDRC method in being able to target an upper bound on the false discovery rate, and therefore lower bound on precision, without observing labels during training.
For these experiments generate data following mixture of distribution, with share (0, of observations drawn from the anomalous distribution and a share 1 тi drawn from the non- anomalous distribution. We associate label with each observation, if the observation is drawn from the anomalous distribution, 0 otherwise. We then compute p-values of the data under the non-anomalous distribution, mimicking a forecasting-bias anomaly scorer while abstracting away model noise and uncertainty.
We apply the different FDRC methods described above to these sequences of p-values in order to classify observations as anomalous or not. We use the labels to compute the false discovery rate, decaying false discovery rate, well as statistical power. We focus here assessing the pure decay version. The appendix contains further experiments taking local dependency into account.
Figure shows that our methods, labelled DecayLord and DecaySaffron are able to control the FDR; as anomalies become rarer (bottom panel) while maintaining power (top panel) ensuring that substantial fraction of anomalies are detected. Expectedly, having power against vanishingly rare

---

Power [Foeaall
2.1
Adda
Drsgfood
Proportion Anomaliess
Terpd
Daagfaad
FDR [--Protision]
DonsSeffie
124
Proportion Anomalios
FDRt, [1-Prettsion)
035
Proportina Anonaliss my
Figure 3: Power (recall) and FDR (1 precision) changes according to anomaly proportions. For each anomaly proportion, 100 datasets of length 20K are generated by drawing from either (0, 1) with probability (1 Ti) or from (0,03) 3) with probability #1 where и1 E 110-1,0.9, For all models, the target FDR is 0.1; for SAFFRON, = 1/2, and for ADDIS 1/4. We set to 0.99 for DecayLord and DecaySaffron models.
alternatives comes at the cost a decrease in precision (middle panel). The power (or recall) of non-decay methods tends to zero rapidly as the a-death phenomenon prevents them from making any rejections. Their precision, (1 -FDR), remains artificially high since no discovery is ever made.
We provide an additional experiment with artificial data in Appendix A It compares the Power/FDR curves of our algorithms to popular existing techniques.
6.2 Real World Experiments
We next demonstrate the performance of our methods p-values generated by simple forecaster applied on the Server Machine Dataset (SMD) 28). The p-value for each observation calculated by assuming that the data follows a Gaussian distribution whose moments are estimated as the sample mean and standard deviation of the previous n points. This naive p-value generation method does not attempt control for dependence in the time-series, potentially introducing dependence in the p-values. The SMD is composed of multi-dimensional time series, labels are affixed to the whole dataset for specific time-stamp rather than to individual series. Therefore, the p-values assign to a given time-stamp is the smallest of the p-values computed on each dimension for that time-stamp. Anomalies relatively frequent in the SMD, 4.16% of anomalous. this setting, both standard and decay version of FDRC rules are expected to perform well.
labelled as
Figure shows that while both decay and non-decay versions L.RD and SAFFRON not con- trol the target FDR very precisely (top-left), they control the decay FDR much more accurately (top-

---

Acsal 3chooseee
Doarathe Gab
FDX 11 (.Pandiiaa)
Power
Doatod
Thage (heairrs))
EDB (-Peensenn)
Figure 4: FDR, FDR, and Power(recall) changes according to target FDR over the p-values gener- ated by applying a simple forecast algorithm to the Server Machine Dataset. The bottom right plot shows the power change according actual FDR is given.
right). DecayLord and DecaySaffron has higher power that non-decay versions when the target FDR is low (bottom-left). For given, realized false discovery rate, the power of both DecayLord and DecaySaffron is higher (bottom-right).
Conclusion, Limitations, and Future Work
This article demonstrates that by using memory decay procedure, the-art online false discovery rate control rules can maintain power against rare alternatives. This enables the use of FDRC methods for anomaly detection tasks in streams of time-series data.
ensure that state-of-
This work is limited in scope to demonstrating theory and empirically that our modified FDRC rules effective. We do not consider the problem of tuning the hyper-parameters of these rules, in particular the decay rate as well as the selection of the sequence 7t. The choice of these parameters likely to noticeably influence the performance of the the rules.
We have chosen not to explore the coupling of these rules with anomaly scoring models to evaluate the efficiency of these pairs on real-world anomaly detection tasks the purpose of this article is on establishing the properties of these rules. In addition, we note that commonly used public data sets to evaluate anomaly detection methods have been convincingly argued (32] to be flawed and not representative real-world tasks in particular due an unrealistically high density of anomalies. In such settings, and contrary to many practical problems in anomaly detection, using memory decay FDRC rules would not be useful. We hope to be able to follow up on this work once higher-quality public datasets become available.
10

---

References
[1] Ehud Aharoni and Saharon Rosset. Generalized o-investing: definitions, optimality results and application to public databases. Journal of The Royal Statistical Society Series B-statistical Methodology, 76, 2014.
[2] Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: a practical and pow- erful approach multiple testing. Journal of the Royal statistical society: series B (Method- ological), 57(1), 1995.
[3] Yoav Benjamini and Daniel Yekutieli. The control of the false discovery rate in multiple testing under dependency. Annals of statistics, 2001.
[4] Jasmin Bogatinovski, Sasho Nedelkoski, Alexander Acker, Florian Schmidt, Thorsten Wit- tkopp, Soeren Becker, Jorge Cardoso, and Odej Kao. Artificial intelligence for it operations (aiops) workshop white paper, 2021.
[5] G. E. Box, G. M. Jenkins, and F. MacGregor. Some recent advances in forecasting and control. Journal of the Royal Statistical Society. Series C (Applied Statistics), 23, 1974.
[6] Mohammad Braei and Sebastian Wagner. Anomaly Detection in Univariate Time-series: A Survey on the State-of-the-Art. arXiv e-prints, 2020.
[7] Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey, ACM computing surveys (CSUR), 41, 2009.
[8] Emmanuel de Bézenac, Syama Sundar Rangapuram, Konstantinos Benidis, Michael Bohlke- Schneider, Richard Kurle, Lorenzo Stella, Hilaf Hasson, Patrick Gallinari, and Tim Januschowski. Normalizing kalman filters for multivariate time series analysis. Advances in Neural Information Processing Systems, 33, 2020.
[9] Ralph Foorthuis. On the nature and types of anomalies: a review of deviations in data. Inter- national Journal of Data Science and Analytics, 2021.
[10] Dean Foster and Robert Stine. Alpha-investing: A procedure for sequential control of expected false discoveries. Journal of the Royal Statistical Society Series B, 70, 04 2008.
[11] Sudipto Guha, Nina Mishra, Gourav Roy, and Okke Schrijvers. Robust random cut forest based anomaly detection on streams. In Proceedings The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, 2016.
[12] Nicholas A Heard and Patrick Rubin-Delanchy. Choosing between methods of combining p-values. Biometrika, 105, 2018
[13] Y. Hochberg and A. Tamhane. Multiple Comparison Procedures. John Wiley, 1987.
[14] Rob Hyndman, Anne Koehler, Keith Ord, and Ralph Snyder. Forecasting with exponential smoothing. The state space approach. Springer, 01 2008.
[15] Adel Javanmard and Andrea Montanari. On Online Control of False Discovery Rate. arXiv e-prints, 2015.
[16] Adel Javanmard and Andrea Montanari. Online rules for control of false discovery rate and false discovery exceedance. The Annals of Statistics, 46, 03 2018.
[17] Nicolai Meinshausen, Lukas Meier, and Peter Bühlmann. P-values for high-dimensional re- gression. Journal of the American Statistical Association, 104(488), 2009.
[18] Aaditya Ramdas, Fanny Yang, Martin J Wainwright, and Michael I Jordan. Online control of the false discovery rate with decaying memory. In Advances Neural Information Processing Systems, volume 30, 2017.
[19] Aaditya Ramdas, Tijana Zmic, Martin Wainwright, and Michael Jordan. Saffron: an adaptive algorithm for online control of the false discovery rate. In International conference on machine learning, 2018
11

---

[20] Hansheng Ren, Bixiong Xu, Yujing Wang, Chao Yi, Congrui Huang, Xiaoyu Kou, Tony Xing, Mao Yang, Jie Tong, and Qiang Zhang. Time-series anomaly detection service at microsoft. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
[21] Shiblee Sadik and Le Gruenwald. Research issues in outlier detection for data streams. SIGKDD Explorations Newsletter, 15, 2014.
[22] David Salinas, Michael Bohlke-Schneider, Laurent Callot, Roberto Medico, and Jan Gasthaus. High-dimensional multivariate forecasting with low-rank gaussian copula processes. In Ad- vances in Neural Information Processing Systems, volume 32, 2019.
[23] David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. Deepar: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting, 36, 2020.
[24] Matthias W Seeger, David Salinas, and Valentin Flunkert. Bayesian intermittent demand fore- casting for large inventories. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, 2016.
[25] Dominique T. Shipmon, Jason M. Gurevitch, Paolo M. Piselli, and Stephen T. Edwards. Time Series Anomaly Detection; Detection of anomalous drops with limited features and sparse examples in noisy highly periodic data. arXiv e-prints, August 2017.
[26] Alban Siffer, Pierre-Alas Alain Fouque, Alexandre Termier, and Christine Largouet. Anomaly de- tection in streams with extreme value theory. In Proceedings of the 23rd ACM SIGKDD Inter- national Conference on Knowledge Discovery and Data Mining, 2017.
[27] John Storey. A direct approach to false discovery rates. Journal of the Royal Statistical Society Series B, 64, 08 2002.
[28] Ya Su, Youjian Zhao, Chenhao Niu, Rong Liu, Wei Sun, and Dan Pei. Robust anomaly detec- tion for multivariate time series through stochastic recurrent neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
[29] Wenguang Sun and T. Tony Cai. Oracle and adaptive compound decision rules for false dis- covery rate control. Journal of the American Statistical Association, 102, 2007.
[30] Jinjin Tian and Aaditya Ramdas. Addis: an adaptive discarding algorithm for online fdr control with conservative nulls. In NeurlPS, 2019.
[31] Weinan Wang. Online fdr controlled anomaly detection for streaming time series. In 5th Workshop on Mining and Learning from Time Series (MiLe7TS), 2019.
[32] Renjie Wu and Eamonn Keogh. Current time series anomaly detection benchmarks are flawed and are creating the illusion of progress. IEEE Transactions on Knowledge and Data Engi- neering, 2021.
[33] Tijana Zmic, Daniel L. Jiang, Aaditya Ramdas, and Michael I. Jordan. The power of batching in multiple hypothesis testing. In AiSTATS, 2020.
[34] Tijana Zrnic, Aaditya Ramdas, and Michael I Jordan. Asynchronous online testing of multiple hypotheses. Journal of Machine Learning Research, 22(33), 2021.
12


Reviews:
[{"review_id": "un0uyBvpDYu", "reviewer": "Reviewer_trQ6", "summary": "This paper discusses techniques by which some limitations of current online false discovery rate control algorithms can be overcome. Importantly, the sequential decision thresholds from current algorithms decay to zero in the absence of recent rejections of the null hypothesis -- a situation called alpha-death. A technique to overcome this is proposed.\n\n================\nUpdate: The scope of contribution has been clarified in the rebuttal. The authors address the lack of real-world experiments somewhat, but more is desired to improve the strength of the paper.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. It was a bit hard to figure out the main novel contribution in this paper. It seems that the equation after line 216 (smoothed FDR) is the claimed contribution, but since the equation is not numbered, it does not come out clearly. Moreover, most equations on page 8 are also unnumbered and perhaps part of the contribution of this paper. All these are minor variations over existing techniques.\n\n2. The experiments section (line 275) states that the paper does not aim to show that the technique results in yielding higher anomaly detection accuracy than alternatives. This is a serious drawback and coupled with the fact that no real-world datasets have been used perhaps the paper in its current state is only fit for a workshop rather than a full conference.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations have been discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Xt3Cfrbfxa", "reviewer": "Reviewer_SufA", "summary": "This paper proposes novel rules for false discovery rate control (FDRC) for online anomaly detection in time series ", "questions": "", "limitations": "", "rating": 9, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is slightly out of my area, so this will be a low confidence review. In particular, I cannot strongly comment on the novelty.\n\nHaving said that, this is clearly the best paper in my bunch (of seven). Well motivated, very well written and possessing deep insights in statistics.  The paper clearly identifies its limitations \n\nThe paper ends with “We hope to be able to follow up on this work once higher-quality public datasets become available.” I would love to see this (long journal) paper, I think it would be a very useful resource for the community. However, within the page limits available this current work makes a strong contribution. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "IxU3Oi6OCtg", "reviewer": "Reviewer_xktj", "summary": "This research seeks to control the false-discovery rate, while simultaneously avoiding alpha-death, where the alpha values are shrunk to near zero for multiple-hypothesis testing with extremely rare events. The authors propose a method based on memory-decay that is extensible to other algorithms of the alpha-investing class.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper was well structured in setting up the problem, detailing the previous work and limitations, providing a solution and an extension, and providing experimental results. The exeprimental results could be fleshed out more, although I have trouble deciding from where the extra room would have come, besides perhaps the \"False discovery rate control\" section or removing some of the formulations in the \"Oracle rules\" section. \n\nOverall, I believe their extensible decay contributions to be useful to the field. I believe this research provides ample starting point for others, or the authors themselves, to explore.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did an adequate job of discussing the limitations of their research.There were no obvious potential negative societal impacts that I believe the authors missed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "5QEKOKpPRoX", "reviewer": "Reviewer_4PWU", "summary": "This paper address online false discovery rate (FDR $\\simeq 1-\\mathrm{Precision}$) control in anomaly detection, where we obtain observations sequentially and immediately decide whether we classify them into anomaly or not.\nThe authors adopted smoothed FDR (sFDR) for criteria and then derived rejection thresholds that offer high detection power (Recall) for anomalies without shrinking its detection threshold to zero while maintaining target sFDR. It is made possible by the fact that FDR for no rejection is defined by the explicit parameter $\\eta$ in the sFDR.\nThey also proposed a way to handle local dependency in time-series with a similar procedure.\nExperimental results on synthetic datasets demonstrate that the proposed method performs better than existing methods, especially when an anomaly is very rare.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality:\n* This work proposed novel rejection thresholds, $\\alpha_t$s, in Eqs. (8) and (9) for anomaly detection with a capability of online FDR control. It is derived from well-studied sFDR [18].\n\n### Quality:\n* Related work is well-written and would be informative for many readers.\n\n* Experimental evaluation is weak.\n    - It is only on synthetic datasets.\n    - They even did not conduct experiments on time-series or sequential data.\n    - It seems that in cases where anomalies are rare, the system worked well. However, in cases where anomalies are more common, the performance deteriorates. I would still like to see how the proposed method works in real data, especially in more realistic scenario where we consider decay and local dependency.\n    - The authors stated that \"The appendix contains further experiments taking local dependency into account.\" in l.288, but there would be no such experiment in the appendix. I guess that they had tried to add experiments after submission but they could not. It could be unfair.\n\n### Clarity:\n* They did not clearly state the contributions of this paper. It would be better to state them.\n\n* It would be better to cite conference/journal not arXiv, such as [23] is published in Neurips2019 and [32] is published in AISTATS2020.\n\n* In l.142, what is \"reward\" in this context?\n\n* In l.267, sFDR would be mFDR?\n\n* Figure 2 is not mentioned in the main text. Also, in general, it is better to locate figures on top.\n\n### Significance:\n* The proposed method could be practically imoportant since it offers high recall for anomalies while maintaining target precision. However, the significance on real data is not clear because they did not provide experiments on real datasets.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They addressed the limitations and potential negative social impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After the rebuttal phase, the paper now has only positive reviews, and as such could 
be accepted. The main issues found during the review phase are the somewhat unclear novelty
and the insufficient experiments. After carefully reading the paper again, I need to add 
another concern: the independence assumption of the p-values. While the authors try to 
address this issue in Section 5, their approach is somewhat limited:

- It is assumed that sufficiently far away p-values are independent, this is measured by the 
  distance L in time, see (10). However, it remains unclear whether and when this assumption is satisfied,
  and the authors do not discuss this issue.
  
- The only proposed method working for (10) needs to know L, which again sounds rather unrealistic.

In summary, despite having a good average rating and a positive rebuttal phase, I personally see 
this as a true borderline case.
Decision: Accept (Poster)