# Experimental beating the standard quantum limit under non-markovian
dephasing environment

Huan Cao  CAS Key Laboratory of Quantum Information, University of Science and
Technology of China, Hefei, 230026, China  University of Vienna, Faculty of
Physics, Vienna Center for Quantum Science and Technology (VCQ) and Research
platform TURIS, Boltzmanngasse 5, 1090 Vienna, Austria  CAS Center For
Excellence in Quantum Information and QuantumPhysics, Hefei, 230026, China
Christian Doppler Laboratory for Photonic Quantum Computer, Faculty of
Physics, University of Vienna, Sensengaasse 8, 1090 Vienna, Austria  Chao
Zhang<EMAIL_ADDRESS>CAS Key Laboratory of Quantum Information,
University of Science and Technology of China, Hefei, 230026, China  CAS
Center For Excellence in Quantum Information and QuantumPhysics, Hefei,
230026, China  Hefei National Laboratory, University of Science and Technology
of China, Hefei 230088, China  Yun-Feng Huang<EMAIL_ADDRESS>CAS Key
Laboratory of Quantum Information, University of Science and Technology of
China, Hefei, 230026, China  CAS Center For Excellence in Quantum Information
and QuantumPhysics, Hefei, 230026, China  Hefei National Laboratory,
University of Science and Technology of China, Hefei 230088, China  Bi-Heng
Liu  CAS Key Laboratory of Quantum Information, University of Science and
Technology of China, Hefei, 230026, China  CAS Center For Excellence in
Quantum Information and QuantumPhysics, Hefei, 230026, China  Hefei National
Laboratory, University of Science and Technology of China, Hefei 230088, China
Chuan-Feng Li<EMAIL_ADDRESS>CAS Key Laboratory of Quantum Information,
University of Science and Technology of China, Hefei, 230026, China  CAS
Center For Excellence in Quantum Information and QuantumPhysics, Hefei,
230026, China  Hefei National Laboratory, University of Science and Technology
of China, Hefei 230088, China  Philip Walther  University of Vienna, Faculty
of Physics, Vienna Center for Quantum Science and Technology (VCQ) and
Research platform TURIS, Boltzmanngasse 5, 1090 Vienna, Austria  Christian
Doppler Laboratory for Photonic Quantum Computer, Faculty of Physics,
University of Vienna, Sensengaasse 8, 1090 Vienna, Austria  Guang-Can Guo  CAS
Key Laboratory of Quantum Information, University of Science and Technology of
China, Hefei, 230026, China  CAS Center For Excellence in Quantum Information
and QuantumPhysics, Hefei, 230026, China  Hefei National Laboratory,
University of Science and Technology of China, Hefei 230088, China

###### Abstract

Entanglement enhanced quantum metrology has been well investigated for beating
the standard quantum limit (SQL). However, the metrological advantage of
entangled states becomes much more elusive in the presence of noise. Under
strict Markovian dephasing noise, the uncorrelated and maximally entangled
states achieve exactly the same measurement precision. However, it was
predicted that in a non-Markovian dephasing channel, the entangled probes can
recover their metrological advantage. Here, by using a highly controlled
photonic system, we simulate a non-Markovian dephasing channel that fulfills
the quadratic decay behaviour. Under such a channel, we demonstrate that the
GHZ states can surpass the SQL in a scaling manner, up to six photons. Since
the quadratic decay behavior is quite general for short time expansion in open
quantum systems (also known as the quantum Zeno effect), our results suggest a
universal and scalable method to beat the SQL in the real-word metrology
tasks.

The harness of quantum technologies revolutionizes the information processing.
Quantum techonological applications has now been developed into a
unprecedented stage and may greatly surpass many current approaches, typically
in the domain of quantum computation [1], quantum communication [2, 3] and
quantum metrology [4]. To estimate the unknown parameter of the embedded
field, the classical strategy of employing $N$ uncorrelated particles will
yield the estimation resolution at the particle number scaling of
$\triangle^{2}\omega\propto N^{-1}$, which, restricted by central limit
theorem, is known as the standard quantum limit (SQL) or shot-noise limit
scaling [5, 6]. Quantum metrology indicates a more favorable solution, which
leverages the entangled states as probes, surprisingly resulting in an
ultimate limit of estimation resolution known as Heisenberg limit (HL)
$\triangle^{2}\omega\propto N^{-2}$ [4, 7]. Several experimental works have
demonstrated the outperformance of quantum metrological stategy over classical
one, including diverse quantum system such as four-photon [8], three trapped-
ions [9] and 10-spin symmetric modules [10].

Entanglement is generally recognized as an crucial ingredient in quantum
metrology, and the maximally-entangled NOON state (such as Greenberger-Horne-
Zeilinger (GHZ) state) is typically required for beating the SQL. However, a
quantum system will inevitably interact with surroundings. The open system
dynamics make the entangled resource gradually lose its quantum property,
eventually degrading the quantum enhancement. It is particularly demanding to
investigate how to outperform the SQL in noisy quantum metrology. It has been
proven that most types of local Markovian noise, which is usually encountered
in experiment, including losses, depolarization, spontaneous emission, both
GHZ and product state could only yield an asymptotic SQL-like scaling [11, 12,
13, 14]. Even for the optimized choice of preparation measurement, the quantum
advantages provide only constant enhancement. Nevertheless, a variety of
seminal results regarding the transversal noise - that is, the direction of
noise operator is perpendicular to the Hamitonian dynamics - are presented
theoretically [15, 16] and experimentally [17]. Beating the SQL scaling in
parameter estimation can be addressed with passive measurement by optimizing
the interaction time. Moreover, provided with the Hamiltonian-not-in-Lindblad-
span (HNLS) condition hold, the Heisenberg limit scaling is attainable by
actively repetitive quantum error correction (QEC) [18, 19, 20, 21].
Immediately following the theoretical work, quantum metrology enhanced by two-
step QEC is experimentally demonstrated in nitrogen-vacancy (NV) center spin
register [22], displaying the resilience against transversal noise.

When considering the parallel noise, e.g. the Hamiltonian dynamics and noise
operator are both along $z$-direction (dephasing noise), entanglement
advantage is turned out to be an elusive goal, which hampers many developments
in the field. Huelga et al. conclude that the GHZ state and product state
could both exhibit SQL-like scaling when subject to Markovian dephasing [23].
However, it is still possible to show quantum enhancement and outperform SQL
in parallel noise. Later it was shown that GHZ state can surpass the SQL, and
even achieving the Zeno limit scaling $\triangle^{2}\omega\propto N^{-3/2}$ if
the dephasing noise is non-Markovian with quadratic decay behaviour which
features initial quantum Zeno effect [24, 25]. The entangled probes provide
metrological advantages over uncorrelated probes, which is in marked contrast
with Markovian noise case where a small mount of noise would restore the
scaling into SQL.

In this letter, we adopt a succinct photonic method to implement the local
non-Markovian dephasing models in multipartite photonics system. The quadratic
decay factor $\gamma\left(t\right)\propto t^{2}$, which initially features the
quantum Zeno dynamics, is well simulated in tabletop photonic system. By
choosing the optimal interrogation time and proper measurement operator, we
identify the uncertainty of parameter estimation with the probe number up to
six photons. Our experimental results demonstrate that the GHZ strategy can
surpass the SQL even in the presents of non-Markovian parallel noise.

We start with recalling the quantum metrology task in the presence of
independent parallel noise. With this task we aim to estimate the unknown
frequency $\omega$ embedded in the unitary dynamics with $N-$qubit Hamiltonian
$H=\sum_{i}^{N}H_{i}=\frac{1}{2}\sum_{i}^{N}\omega\sigma_{z}^{i}$, where the
$H_{i}=\omega\sigma_{z}^{i}$ denotes the Pauli-z operator for $i$-th particle.
The time evolution of the system (probes) operator $\rho$ in the presence of
independent parallel noise is formulated with master equation [15, 16]:

$\displaystyle\begin{aligned} \frac{\partial\rho}{\partial
t}&=\mathcal{H\left(\rho\right)}+\mathcal{L\left(\rho\right)}\\\
&=-i\left[H,\rho\right]+\frac{\alpha\left(t\right)}{2}\sum_{i}\left(\sigma_{z}^{i}\rho\text{$\sigma_{z}^{i}$}-\rho\right)\end{aligned}$
(1)

Here $\mathcal{H\left(\rho\right)}=-i\left[H,\rho\right]$ denotes the unitary
dynamics imprinting on the probes, and Liouvillian operator
$\mathcal{L\left(\rho\right)=}\frac{\alpha\left(t\right)}{2}\sum_{i}\left(\sigma_{z}^{i}\rho\text{$\sigma_{z}^{i}$}-\rho\right)$
describes the noise, of which the strength $\alpha\left(t\right)$ closely
relates to the quantum non-markovianity [26, 27]. Notice that the Hamiltonian
$H$ and the noise are both along the $\sigma_{z}$ direction, denoting the
parallel noise. As the noise operator is local and independent, the effect of
noise can also be well described in the single-particle system. We consider
the single-particle system for simplicity. The evolution of single-qubit is
formulated as
$\rho(t)=\begin{pmatrix}\rho_{00}&\rho_{01}e^{iH_{i}t-\gamma(t)}\\\
\rho_{10}e^{-iH_{i}t-\gamma(t)}&\rho_{11}\\\ \end{pmatrix}$ where $\rho_{mn}$
are the density matrix elements of initial state. The decaying terms
$e^{-\gamma(t)}$ fully characterizes the features of dephasing dynamics and is
uniquely determined by interaction strength $\alpha(t)$. Concretely, a time-
independent interaction strength $\alpha(t)$=const in eq.1 represents the
dynamical semigroup map which is treated as typical Markovian map [28, 29].
The characteristic behavior of the quantum system exhibits the exponential
decay $\gamma(t)\propto t$. The merit of our work is based on the time varied
$\alpha(t)\propto t$, which leads to the quadratic behavior of
$\gamma(t)\propto t^{2}$ that captures the basis of quantum Zeno effect and is
deemed as non-markovian process.

For the uncorrelated probes, each single probe is prepared to the initial
state $\left(\left|0\right\rangle+\left|1\right\rangle\right)/\sqrt{2}$, while
the entangled probes are prepared to the $N$-qubit GHZ state
$\left(\left|0\right\rangle^{\otimes N}+\left|1\right\rangle^{\otimes
N}\right)/\sqrt{2}$. The unknown frequency $\omega$ is estimated based on the
average value of an operator, here we chose the parity operator
$P_{x}=\sigma_{x}^{\otimes N}$ which is optimal for GHZ probes in noiseless
case.

Figure 1:  Sketch of the experimental setup. (a) Three ERP-pairs are generated
through SPDC process with three sanwiched beam-like type II $\beta-$barium
borate (BBO) sources. The spatial compensation crystal (TC) and temporal
compensation crystal (SC) make the two possible ways of generating SPDC
photons with BBOs of single resource indistinguishable, so that the EPR state
$\left(\left|00\right\rangle+\left|11\right\rangle\right)/\sqrt{2}$ is
generated in each source. Three extraordinary photons are fed into the PBSs to
complete the cascaded Hong-Ou-Mandel interferences. For N=3,4 GHZ state, the
final BBO source and corresponding PBS are removed. For N=1,2, only the EPR
pairs of the first BBO source is used and no HOM effect required. Then each
photon is spatially filtered by single mode fiber (SMF). (b) Halmitonian
evolution and the coupling between each subsystem and environment. Finally,
each photon is collected by the polarization analysis system consisting of one
QWP, one HWP, one PBS and two single-photon detectors. The HWP-QWP-HWP at
$(22.5,\frac{\theta}{2},22.5)$ enables to imply the phase $e^{i\theta}$ on
single party. The inset describes how the spatial mode evolved in the BD
pairs. PBS: polarization beam splitter; HWP: half wave-plate; QWP: quarter
wave-plate.

Fig. 1 depicts the experimental setup. Three EPR pairs are generated through
Spontaneous parametric down-conversion (SPDC) by sandwiched beam-like cutting
BBO sources [30, 31]. The three extraordinary photons are spatially overlapped
on two PBS, and become temporally indistinguishable by carefully tuning the
photonic arrival time with prisms. This forms a cascaded Hong-Ou-Mandel (HOM)
interferometer. Indistinguishability of the photons guarantees the occurrence
of HOM effect and the GHZ states $\left(\left|0\right\rangle^{\otimes
N}+\left|1\right\rangle^{\otimes N}\right)/\sqrt{2}$ can be generated by post-
selecting the case where there is one and only one photon in each output.
Afterwards, for realization of the desired dephasing channel in the following
step, each photon is coupled into a single-mode fiber (SMF) and exits with the
same adjustable fiber collimator to guarantee the Gaussian beam profile for
the following dephasing simulator. The preparation of N-GHZ probes and spatial
mode is visualized in the Fig. 1(a).

Next, each party of GHZ probes is fed into an independent channel which
comprises of an unitary dynamics $\mathcal{H\left(\rho\right)}$ and an
interaction induced dephasing operator $\mathcal{L\left(\rho\right)}$ (Fig.
1)(b). Since the $\mathcal{H\left(\rho\right)}$ and
$\mathcal{L\left(\rho\right)}$ are commutative, they can be imprinted
independently. This could also be deduced with the expression of $\rho(t)$. As
shown in Fig. 1(a), each photon first passes through a combination of HWP-QWP-
HWP which applies a dynamical phase into the GHZ states to simulate the
unitary $e^{iHt}$. Then the photon undergoes a pair of thin beam-displacers
(BDs) (inset in Fig.1) to simulate the non-Markovian dephasing noise. We
encode the photonic polarization as system and the spatial mode as
environment. The BD pairs consist of two BDs with identical thickness of
$\ell$ and perpendicular optical axis to each other. When the photons pass
through the BD pairs, the system and environment is coupled, leading to
deflection along horizontal (vertical) direction according to the horizontal
(vertical) polarization. For displacement distance $x_{0}/\sqrt{2}$ of each
BD, the distance between different polarizations is $x_{0}$. The coupling
leads to partial distinguishability of polarization and decoherence of the
system by tracing out the environment (spatial mode). Suppose a Gaussian
intensity distribution of spatial mode
$\Lambda(x,y;\omega)=\frac{1}{2\pi\omega^{2}}e^{-\frac{x^{2}+y^{2}}{\omega^{2}}}$,
where x(y) is Cartesian coordinates and $\omega$ is beam waist, evolution of
aforementioned BD pairs suffices to imprint the quadratic decay behaviors
$e^{-\gamma(t)}=e^{-\frac{x_{0}^{2}}{2\omega^{2}}}$. In the experiment we set
$\gamma\left(t\right)=t^{2}$, and then the time evolution can be related with
the thickness $\ell$ of the BD pairs with the relation
$t=\frac{x0}{\omega},x_{0}=\frac{\sqrt{2}}{9.4103}\ell$. See section I of
supplemental materials for detailed descriptions.

The frequency $\omega$ is estimated based on the average value of $P_{x}$, the
mean-square error of $\omega$ can be deduced from error propagation
$\triangle^{2}\omega=\left(\triangle^{2}P_{x}\right)/\left|\partial\left\langle
P_{x}\right\rangle/\partial\omega\right|^{2}=\left(1-\left\langle
P_{x}\right\rangle^{2}\right)/\left|\partial\left\langle
P_{x}\right\rangle/\partial\omega\right|^{2}$ (since $\langle
P_{x}^{2}\rangle=1$). If the measurement is repeated $\upsilon$ times, the
frequency resolution will also reduce by a factor of $\upsilon$. We are
interested in the performance of frequency estimation over a total time T with
a single-round interrogation time t, thus $\upsilon$=T/t. The time normalized
frequency resolution can be written as

$\triangle^{2}\omega T=t\frac{1-\langle
P_{x}\rangle_{t}}{\left|\partial\left\langle
P_{x}\right\rangle_{t}/\partial\omega\right|^{2}}$ (2)

which means we fix the consumption of time resource and consider only the
scaling manner with respect to the particle number. In the noiseless case, the
longer the evolution time, the more information can be extracted about the
parameter. However, for noisy cases, there is always an optimal interrogation
time to minimize Eq.5. For N-qubit GHZ probes, we can calculate the optimal
interrogation time to be $t^{opt}=\sqrt{\frac{1}{4N}}$ of our noise model (see
section III of Supplemental Material for details).

Figure 2:  (a)-(f) The mean value of $P_{x}$ with respect to GHZ state with
$N=1\cdots 6$. The horizontal axis denotes the phase $\omega t_{e}$ imprinted
on each subsystem. The dots represent our experimental data while the lines
are the sinusoidal fitting lines. The $\frac{\partial\left\langle
P_{x}\right\rangle}{\partial\omega}$ is estimated throught the derivative of
fitting line at optimal interrogation point.

To experimentally measure the partial derivative, we vary the relative phase
$\theta$ ($\theta=\omega t^{opt}$) for each photon from 0 to $\pi$ and get the
fringe of the mean value of $P_{x}$. Theoretically, the $\langle P_{x}\rangle$
can be described with cosine function of $\langle
P_{x}\rangle=\cos\left(N\omega t\right)e^{-N\gamma\left(t\right)}$. The
measured data are depicted in Fig. 2. Each subplot denotes the fringe of
N-partite GHZ state with the photon number from N=1 to 6. We fit the data
points to a cosine curve according to the theoretical evolution of $\langle
P_{x}\rangle_{t}$. Next the partial derivative $\frac{\partial\langle
P_{x}\rangle_{t}}{\partial\omega}$ at optimal sensitivity point
($\theta=\frac{k\pi}{2N},k\ odd$) can be estimated. We also determine the
partial derivative by using the five-point stencil method without the
assumption of the evolution function of $\langle P_{x}\rangle_{t}$. The
results fulfill with the curve fitting results very well (see section II of
Supplemental Material for details).

Figure 3:  (a) describes the frequency resolution $\triangle^{2}\omega T$ in
log(N)-log$(\triangle^{2}\omega T)$ plot, with the red, blue, yellow solid
lines respectively representing the SQL, ZL and HL. The dotted line denotes
the fitted line with our experimental data. (b) The pillars shows the Fisher
information per photon $1/N\triangle^{2}\omega T$ with qubit number from $N=1$
to $N=6$. Theoretical bound of Fisher information for N=1 is presented as
dotted line, in accordance with SQL. The Fisher information for $N=1\cdots 6$
is $(0.2884\pm 0.0003,0.3861\pm 0.0001,0.3861\pm 0.0031,0.4480\pm
0.0025,0.4393\pm 0.0148,0.4774\pm 0.0155)$. The Fisher information of all the
entangled probe surpass SQL bound 0.3033. In (a)(b), the errorbars of data
accounts for the Poisson-distributed of finite photon statistics, which is
calculated by Monte Carlo simulations. Corresponding data with noise
subtraction are provided in the inset.

Afterwards, the optimal frequency resolution $\triangle^{2}\omega T$ is
calculated and displayed in the Fig. 3(a) in logarithmic coordinate. It shows
that the results for entangled GHZ probes can beat the SQL (red line, with the
slop of -1). Moreover, we calculate the Fisher information per photon
$F_{N}=(N\triangle^{2}\omega T)^{-1}$, which quantifies the extractable
informativeness of the parameter per qubit. The results are shown in Fig.3(b),
from which we see the quantity increases with the entangled GHZ probe size,
thus indicating a scalable metrological advantage can be achieved. Note that
due to the imperfect preparation of GHZ state, the observed frequency
resolution is less than the Zeno limit $N^{-3/2}$ (ZL, the blue line)
predicted by ideal entangled probes. Also, the Fisher information per photon
for $N=3$ ($N=5$) cannot exceed $N=2$ ($N=3$). Because for $N=3$ ($N=5$), new
EPR pair is introduced and an additional HOM interference is incorporated,
which is the main noise in our preparation setup. In our experiment, we also
measure the mean value of $P_{x}$ before evolution, the results are
$\left\langle P_{x}\right\rangle_{t=0}=0.9776\pm 0.0001,0.9781\pm
0.0001,0.8777\pm 0.0057,0.8671\pm 0.0067,0.8071\pm 0.0198,0.7968\pm 0.0189$,
for N=1 to 6 GHZ states. The $\langle P_{x}\rangle$ undergoes a drop when new
EPR pairs are introduced. The deviation from the ideal case $\left\langle
P_{x}\right\rangle_{t=0}=1$ will deteriorate the interference visibility of
the fringe (or equivalently $\frac{\partial\left\langle
P_{x}\right\rangle}{\partial\omega}$) and eventually degrade the resolution.
We exclude the preparation imperfection by dividing the data points in Fig.2
by a factor of $\left\langle P_{x}\right\rangle_{t=0}$. After subtracting the
preparation noise, the results are shown in the insert of Fig.3. We fit the
obtained resolution to a line, which yields the slop of $-1.5126\pm 0.0147$,
which agrees with the Zeno limit very well. The increase of the GHZ probe size
will inevitably lead to degrading of the performance, and finally undermines
the quantum advantages. We expect that this difficulty can be overcome by
future quantum error correction techniques. In section V of Supplemental
Material, we analyze the bound of beating SQL with respect to the imperfect
scaled probes.

The main reason the entangled probes can achieve metrological advantage in the
above noise model is due to the quadratic decay behaviour
$\gamma\left(t\right)\propto t^{2}$ of the noise. Such decay factor makes the
entangled probes achieve their optimal interrogation time much shorter than
the uncorrelated ones, and thus can experience a suppressed level of
decoherence, which means they can benefit more from the non-Markovian
environment. However, as mentioned in Ref.[24, 32], the short time quadratic
behavior of $\gamma\left(t\right)$ is not a specific feature of our chosen
noise model, but can be derived directly from a short time expansion of the
Schrodinger evolution, with the only hypotheses of normalizability of the wave
function and finite energy of the initial state. Such a universal decay factor
is the fundamental basis of the quantum Zeno effect [33, 34, 35].
Consequently, our results indicate for almost all noise sources in real-world
open quantum systems, which is the consequence of unitary evolution of the
system-environment state, the SQL can be surpassed by using entangled probes
with a relatively simple preparation and measuring protocol.

In conclusion, our experiment extends the scope of quantum metrology in noisy
circumstance into the parallel noise scenario and demonstrates that the SQL
can be surpassed under non-Markovian dephasing noise by using GHZ probes up to
six qubit. The key point is to probe the system on time scales faster than the
coherence time of the environment. By subtracting the preparation noise in the
GHZ probes, we observe the frequency resolution fulfill the Zeno limit
$N^{-3/2}$ very well, which means the precision can be improved by a factor of
$N^{-1/2}$ by using entangled probes. Since the noise model investigated here
is quite general, our results suggest a universal and scalable method to beat
the SQL in real-world settings. Compared to the general active noise control
schemes such as quantum error correction, the protocol we demonstrated here
greatly reduces the required technology by utilizing the non-Markovian effect
of the environment. Besides, the method we developed to simulate the dephasing
channel could in principle simulate a broader kinds of dephasing dynamics by
modulating the spatial mode of the beam. Engineering non-Markovianity has been
shown beneficial for quantum communication and computation tasks [36, 37, 38,
39, 40, 41]. It is an emerging perspective that to explore quantum metrology
for non-Markovian processes. [42, 43]. It is an interesting question to
investigate how metrological advantage can be achieved in a broader kinds of
non-markovian environment, e.g. the dynamics with information backflow from
environment to system [27], or some correlated environment between subsystems
where the non-Markovianity of dynamics is not implicit locally [44].

###### Acknowledgements.

This work was supported by the Innovation Program for Quantum Science and
Technology (No. ZD0202030401), National Natural Science Foundation of China
(Nos. 11734015, 11874345, 11821404, 11904357); the Austrian Science Fund
(FWF): F 7113-N38 (BeyondC), FG 5-N (Research Group); Research Platform for
Testing the Quantum and Gravity Interface (TURIS), the European Commission
(ErBeSta (No.800942)), Christian Doppler Forschungsgesellschaft;
Österreichische Nationalstiftung für Forschung, Technologie und Entwicklung;
Bundesministerium für Digitalisierung und Wirtschaftsstandort.

## References

  * DiVincenzo [1995] D. P. DiVincenzo, Quantum computation, Science 270, 255 (1995).
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang, Quantum computation and quantum information (2002).
  * Bouwmeester and Zeilinger [2000] D. Bouwmeester and A. Zeilinger, The physics of quantum information: basic concepts, in  _The physics of quantum information_ (Springer, 2000) pp. 1–14.
  * Giovannetti  _et al._ [2004] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum-enhanced measurements: beating the standard quantum limit, Science 306, 1330 (2004).
  * Caves [1981] C. M. Caves, Quantum-mechanical noise in an interferometer, Physical Review D 23, 1693 (1981).
  * Yurke  _et al._ [1986] B. Yurke, S. L. McCall, and J. R. Klauder, Su (2) and su (1, 1) interferometers, Physical Review A 33, 4033 (1986).
  * Giovannetti  _et al._ [2006] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum metrology, Physical review letters 96, 010401 (2006).
  * Nagata  _et al._ [2007] T. Nagata, R. Okamoto, J. L. O’Brien, K. Sasaki, and S. Takeuchi, Beating the standard quantum limit with four-entangled photons, Science 316, 726 (2007).
  * Leibfried  _et al._ [2004] D. Leibfried, M. D. Barrett, T. Schaetz, J. Britton, J. Chiaverini, W. M. Itano, J. D. Jost, C. Langer, and D. J. Wineland, Toward heisenberg-limited spectroscopy with multiparticle entangled states, Science 304, 1476 (2004).
  * Jones  _et al._ [2009] J. A. Jones, S. D. Karlen, J. Fitzsimons, A. Ardavan, S. C. Benjamin, G. A. D. Briggs, and J. J. Morton, Magnetic field sensing beyond the standard quantum limit using 10-spin noon states, science 324, 1166 (2009).
  * Demkowicz-Dobrzański  _et al._ [2012] R. Demkowicz-Dobrzański, J. Kołodyński, and M. Guţă, The elusive heisenberg limit in quantum-enhanced metrology, Nature communications 3, 1 (2012).
  * Escher  _et al._ [2011] B. Escher, R. de Matos Filho, and L. Davidovich, General framework for estimating the ultimate precision limit in noisy quantum-enhanced metrology, Nature Physics 7, 406 (2011).
  * Kołodyński and Demkowicz-Dobrzański [2013] J. Kołodyński and R. Demkowicz-Dobrzański, Efficient tools for quantum metrology with uncorrelated noise, New Journal of Physics 15, 073043 (2013).
  * Kolodynski [2014] J. Kolodynski, Precision bounds in noisy quantum metrology, arXiv preprint arXiv:1409.0535 (2014).
  * Chaves  _et al._ [2013] R. Chaves, J. Brask, M. Markiewicz, J. Kołodyński, and A. Acín, Noisy metrology beyond the standard quantum limit, Physical review letters 111, 120401 (2013).
  * Brask  _et al._ [2015] J. B. Brask, R. Chaves, and J. Kołodyński, Improved quantum magnetometry beyond the standard quantum limit, Physical Review X 5, 031010 (2015).
  * Zhang  _et al._ [2019] C. Zhang, T. R. Bromley, Y.-F. Huang, H. Cao, W.-M. Lv, B.-H. Liu, C.-F. Li, G.-C. Guo, M. Cianciaruso, and G. Adesso, Demonstrating quantum coherence and metrology that is resilient to transversal noise, Physical review letters 123, 180504 (2019).
  * Kessler  _et al._ [2014] E. M. Kessler, I. Lovchinsky, A. O. Sushkov, and M. D. Lukin, Quantum error correction for metrology, Physical review letters 112, 150802 (2014).
  * Arrad  _et al._ [2014] G. Arrad, Y. Vinkler, D. Aharonov, and A. Retzker, Increasing sensing resolution with error correction, Physical review letters 112, 150801 (2014).
  * Dür  _et al._ [2014] W. Dür, M. Skotiniotis, F. Froewis, and B. Kraus, Improved quantum metrology using quantum error correction, Physical Review Letters 112, 080801 (2014).
  * Zhou  _et al._ [2018] S. Zhou, M. Zhang, J. Preskill, and L. Jiang, Achieving the heisenberg limit in quantum metrology using quantum error correction, Nature communications 9, 1 (2018).
  * Unden  _et al._ [2016] T. Unden, P. Balasubramanian, D. Louzon, Y. Vinkler, M. B. Plenio, M. Markham, D. Twitchen, A. Stacey, I. Lovchinsky, A. O. Sushkov, _et al._ , Quantum metrology enhanced by repetitive quantum error correction, Physical review letters 116, 230502 (2016).
  * Huelga  _et al._ [1997] S. F. Huelga, C. Macchiavello, T. Pellizzari, A. K. Ekert, M. B. Plenio, and J. I. Cirac, Improvement of frequency standards with quantum entanglement, Physical Review Letters 79, 3865 (1997).
  * Chin  _et al._ [2012] A. W. Chin, S. F. Huelga, and M. B. Plenio, Quantum metrology in non-markovian environments, Physical review letters 109, 233601 (2012).
  * Matsuzaki  _et al._ [2011] Y. Matsuzaki, S. C. Benjamin, and J. Fitzsimons, Magnetic field sensing beyond the standard quantum limit under the effect of decoherence, Physical Review A 84, 012103 (2011).
  * De Vega and Alonso [2017] I. De Vega and D. Alonso, Dynamics of non-markovian open quantum systems, Reviews of Modern Physics 89, 015001 (2017).
  * Breuer  _et al._ [2016] H.-P. Breuer, E.-M. Laine, J. Piilo, and B. Vacchini, Colloquium: Non-markovian dynamics in open quantum systems, Reviews of Modern Physics 88, 021002 (2016).
  * Lindblad [1976] G. Lindblad, On the generators of quantum dynamical semigroups, Communications in Mathematical Physics 48, 119 (1976).
  * Alicki and Lendi [2007] R. Alicki and K. Lendi,  _Quantum dynamical semigroups and applications_ , Vol. 717 (Springer, 2007).
  * Zhang  _et al._ [2015] C. Zhang, Y.-F. Huang, Z. Wang, B.-H. Liu, C.-F. Li, and G.-C. Guo, Experimental greenberger-horne-zeilinger-type six-photon quantum nonlocality, Physical review letters 115, 260402 (2015).
  * Wang  _et al._ [2016] X.-L. Wang, L.-K. Chen, W. Li, H.-L. Huang, C. Liu, C. Chen, Y.-H. Luo, Z.-E. Su, D. Wu, Z.-D. Li, _et al._ , Experimental ten-photon entanglement, Physical review letters 117, 210502 (2016).
  * Crespi  _et al._ [2019] A. Crespi, F. V. Pepe, P. Facchi, F. Sciarrino, P. Mataloni, H. Nakazato, S. Pascazio, and R. Osellame, Experimental investigation of quantum decay at short, intermediate, and long times via integrated photonics, Physical Review Letters 122, 130401 (2019).
  * Itano  _et al._ [1990] W. M. Itano, D. J. Heinzen, J. Bollinger, and D. Wineland, Quantum zeno effect, Physical Review A 41, 2295 (1990).
  * Facchi  _et al._ [2001] P. Facchi, H. Nakazato, and S. Pascazio, From the quantum zeno to the inverse quantum zeno effect, Physical Review Letters 86, 2699 (2001).
  * Fischer  _et al._ [2001] M. Fischer, B. Gutiérrez-Medina, and M. Raizen, Observation of the quantum zeno and anti-zeno effects in an unstable system, Physical review letters 87, 040402 (2001).
  * Bylicka  _et al._ [2013] B. Bylicka, D. Chruściński, and S. Maniscalco, Non-markovianity as a resource for quantum technologies, arXiv preprint arXiv:1301.2585 (2013).
  * Laine  _et al._ [2014] E.-M. Laine, H.-P. Breuer, and J. Piilo, Nonlocal memory effects allow perfect teleportation with mixed states, Scientific reports 4, 4620 (2014).
  * Xiang  _et al._ [2014] G.-Y. Xiang, Z.-B. Hou, C.-F. Li, G.-C. Guo, H.-P. Breuer, E.-M. Laine, and J. Piilo, Entanglement distribution in optical fibers assisted by nonlocal memory effects, EPL (Europhysics Letters) 107, 54006 (2014).
  * Liu  _et al._ [2016] B.-H. Liu, X.-M. Hu, Y.-F. Huang, C.-F. Li, G.-C. Guo, A. Karlsson, E.-M. Laine, S. Maniscalco, C. Macchiavello, and J. Piilo, Efficient superdense coding in the presence of non-markovian noise, EPL (Europhysics Letters) 114, 10005 (2016).
  * Huelga  _et al._ [2012] S. F. Huelga, A. Rivas, and M. B. Plenio, Non-markovianity-assisted steady state entanglement, Physical review letters 108, 160402 (2012).
  * Schmidt  _et al._ [2011] R. Schmidt, A. Negretti, J. Ankerhold, T. Calarco, and J. T. Stockburger, Optimal control of open quantum systems: cooperative effects of driving and dissipation, Physical review letters 107, 130404 (2011).
  * Mirkin  _et al._ [2020] N. Mirkin, M. Larocca, and D. Wisniacki, Quantum metrology in a non-markovian quantum evolution, Physical Review A 102, 022618 (2020).
  * Altherr and Yang [2021] A. Altherr and Y. Yang, Quantum metrology for non-markovian processes, Physical Review Letters 127, 060501 (2021).
  * Laine  _et al._ [2012] E.-M. Laine, H.-P. Breuer, J. Piilo, C.-F. Li, and G.-C. Guo, Nonlocal memory effects in the dynamics of open quantum systems, Physical review letters 108, 210402 (2012).
  * Ringbauer  _et al._ [2018] M. Ringbauer, T. R. Bromley, M. Cianciaruso, L. Lami, W. S. Lau, G. Adesso, A. G. White, A. Fedrizzi, and M. Piani, Certification and quantification of multilevel quantum coherence, Physical Review X 8, 041007 (2018).

## APPENDIX

##  Appendix A Experimental details

SPDC source-. The laser with repetition rate 80 MHz and the central wavelength
of 780 nm first passes through the frequency doubler to generate the 390nm
pumping light for the following SPDC source. The SPDC source in our experiment
is based on BBO-HWP-BBO sandwiched-like structure. Two identical 1-mm thick
BBO crystals have the cutting angle for beam-like type II phase matching,
which would benefit the coupling efficiency for down-converted photon. The
down-converted photon is possible generated in the two BBOs, with the state
$|H\rangle_{e,1}|V\rangle_{o,1}$, where the e,i(o,i) represents the
extraordinary (ordinary) photons of $i$-th qubit. The polarization of photons
generated in the first BBO1 will be rotated by the $45^{\circ}$ true zero
order HWP into the state $|V\rangle_{e,1}|H\rangle_{o,1}$. Finally this two
possible ways (BBO1 and BBO2) are make indistinguishable in spatial and
temporal degree of freedom by the spatial and temporal compensation crystal.
For a fairly comparison in our experiment from N=1 to N=6, we fix the 390 nm
pumping power as 120 mw during the whole experiment, and a 3 nm (8 nm)
spectral filter is applied to each e(o) photon. The corresponding counting
rates for $2,4,6$-fold coincidence is about 120000 Hz, 90 Hz, and 0.07 Hz
respectively.

Characterize the prepared GHZ states-. For the six-photon GHZ state, we also
measure the measurement setting of $\sigma_{z}^{\otimes 6}$, accompanied with
the results of $\sigma_{x}^{\otimes 6}$ we can deduce a lower bound on the
state fidelity according to the two setting entanglement witness

$\mathcal{W}_{\mathrm{GHZ}_{\mathrm{N}}}:=3\mathbb{I}-2\left[\frac{S_{1}^{\left(\mathrm{GHZ}_{N}\right)}+\mathbb{I}}{2}+\prod_{k=2}^{N}\frac{S_{k}^{\left(\mathrm{GHZ}_{N}\right)}+\mathbb{I}}{2}\right]$
(3)

where
$S_{1}^{\left(\mathrm{GHZ}_{\mathrm{N}}\right)}:=\prod_{k=1}^{N}X^{(k)}$,
$S_{k}^{\left(\mathrm{GHZ}_{\mathrm{N}}\right)}:=Z^{(k-1)}Z^{(k)}\quad\text{
for }k=2,3,\ldots,N.$ are stabilizers for GHZ state. The measured result is
$\langle\mathcal{W}_{\mathrm{GHZ}_{\mathrm{6}}}\rangle=-0.7052\pm 0.0198$,
which clearly demonstrates the genuine six-photon entanglement. Then we can
deduce the state fidelity
$F=\langle\mathrm{GHZ}_{6}|\rho_{\mathrm{exp}}|\mathrm{GHZ}_{6}\rangle>(1-\langle\mathcal{W}_{\mathrm{GHZ}_{\mathrm{6}}}\rangle)/2=0.8526\pm
0.0099$.

Simulation the non-Markovian dephasing channels-. For simulation of desired
dephasing dynamics with photonic system, we encode the polarization of photon
as the system and the spatial mode as the environment. A beam displacer (BD)
with deflection distance $x_{0}$ could couple the system and environment and
lead to decoherence of system. Suppose that the optical axis of BD lies in
horizontal axis, the unitary evolution of total system can be described as

$U(x_{0})=|H\rangle\langle H|\otimes|x+x_{0},y\rangle\langle
x+x_{0},y|+|V\rangle\langle V|\otimes|x,y\rangle\langle x,y|$ (4)

where $|H\rangle$($|V\rangle$) is the polarization of system and $|x,y\rangle$
spatial mode with $(x,y)$ coordinate. Another BD with axis in vertical
direction correspondingly deflect the vertical polarization with the distance
$x_{0}$ in vertical direction.

Gnerally, provided with the initial system state $\rho(0)$ and environment
state $|\phi_{e}\rangle$

$\rho(0)=\begin{pmatrix}\rho_{00}&\rho_{01}\\\ \rho_{10}&\rho_{11}\\\
\end{pmatrix},|\phi_{e}\rangle=\int\mathrm{d}x\mathrm{d}y\lambda(x,y;\omega)|x,y\rangle$
(5)

where $\omega$ is the beam waist of photon, the spatial mode intensity
distribution
$\Lambda(x,y;\omega)=|\lambda(x,y;\omega)|^{2}=\frac{1}{2\pi\omega^{2}}e^{-\frac{x^{2}+y^{2}}{\omega^{2}}}$
and satisfies $\int\Lambda(x,y;\omega)\mathrm{d}x\mathrm{d}y=1$. Coupling
between the polarization and spatial mode occur when passing through the BD
crystal. Considering the system alone will result in the dynamical map
represented as

$\displaystyle\rho(x_{0})$ $\displaystyle=$
$\displaystyle\mathrm{Tr}(U(x_{0})\rho U^{\dagger}(x_{0}))$ $\displaystyle=$
$\displaystyle\begin{pmatrix}\rho_{00}&\rho_{01}\mathcal{F}(x_{0})\\\
\rho_{10}\mathcal{F}^{\ast}(x_{0})&\rho_{11}\\\ \end{pmatrix}$

. Where
$\mathcal{F}(x_{0})=\int\mathrm{d}x\mathrm{d}y\lambda^{\ast}(x,y;\omega)\lambda(x-x_{0},y;\omega)=e^{-\frac{x_{0}^{2}}{2\omega^{2}}}$
it Fourier transformation that describes the characteristic behavior of
dephasing dynamics. Obviously, different type of characteristic behavior could
be simulated by engineering proper spatial mode amplitude distribution
$\lambda(x,y;\omega)$.

Notice that using single BD could introduce the decoherence of polarization
due to coupling with spatial mode, but this will also introduce additional
decoherence by temporal distinguishability between polarizations due to
deflection and short coherence time of SPDC photons. To eliminate this
temporal distinguishability, we adopt a pair of thin BD pairs with the same
displacement distance $x_{0}=y_{0}$ that deflect both horizontal(vertical)
polarization along x(y) direction. The BD is made by the calcite crystal which
the cutting angle is set as $\phi=45^{\circ},\theta=90^{\circ}$. Relations
between the thickness of BD $\ell$ and displacement distance $x_{0}$ of BD
pairs (where each BD has a displacement distance $\frac{x_{0}}{\sqrt{2}}$) is
calculated by $x_{0}=\frac{\sqrt{2}}{9.4103}\ell$.

To confirm the validity of the method, we measure the decoherence behavior of
the light with respect to various displacement distance of thin BD pairs. The
beam waist determined by coupler is $\omega=1.05mm$ and the initial light is
set into diagonal basis $|+\rangle=(|H\rangle+|V\rangle)/\sqrt{2}$. The
measured data and decay fringe is given by Table.1 and Fig. 4(a). The tested
results perfectly match the theoretical prediction, which justify the validity
of the simulation method.

Displacement distance $x_{0}$ of each BD | 0.235 | 0.455 | 0.52 | 0.74 | 1.04 | 1.26 | 1.56 | 1.78
---|---|---|---|---|---|---|---|---
Intensity of projector $|+\rangle\langle+|$ | 4.09 | 3.91 | 3.82 | 3.4 | 2.9 | 2.63 | 2.33 | 2.21
Intensity of projector $|+\rangle\langle+|$ | 0.116 | 0.381 | 0.471 | 0.836 | 1.37 | 1.64 | 1.87 | 1.97
Table 1: Relations between the thickness of BD pairs and dephasing behavior.
Figure 4:  (a)Decays behavior measured with various thickness of BD pairs and
classical light. The dots denotes the tested data and the solid line is
theoretical prediction. (b)sketch of the dephasing setup. The azure arrow
represents the optical axis of BD. For a single BD with displacement distance
$x_{0}/\sqrt{2}$, a pairs of BD enable to separate two polarizations with
distance $x_{0}$.

##  Appendix B Determine the partial derivative and Fisher information via
five-point stencil

The first derivative of a function $f$ at a point $x$ can be approximated by
using five-point stencil method

$f^{\prime}(x)\approx\frac{-f(x+2h)+8f(x+h)-8f(x-h)+f(x-2h)}{12h}.$ (7)

where $h$ is the grid length. The error of this approximation is of the order
$h^{4}$, which can be obtained from Taylor expansion of the right-hand side.

We also use this method to determine the partial derivative
$\frac{\partial\left\langle
P_{x}\right\rangle_{t}}{\partial\theta}|_{t=t^{opt}}$ without the assumption
of the evolution function of the mean value of parity operator $P_{x}$. In the
experiment, by increasing the phase of each photon from zero, the mean value
of $P_{x}$ will undergo oscillations. Then we choose five $\theta$ (data from
Fig.2 in main text) around the optimal sensitivity point
$\theta=\frac{\pi}{2N}$ to calculate the partial derivative. The grid length
is
$\delta\theta=\\{\frac{\pi}{24},\frac{\pi}{24},\frac{\pi}{24},\frac{\pi}{24},\frac{\pi}{20},\frac{\pi}{24}\\}$
for $N=1-6$. The Fisher information per photon
$F_{N}=\left(\frac{\partial\left\langle
P_{x}\right\rangle_{t}}{\partial\theta}|_{t=t^{opt}}\right)^{2}t^{opt}/N$ is
calculated to be $\\{0.2938\pm 0.0042,0.3842\pm 0.0014,0.4217\pm
0.0210,0.4354\pm 0.0110,0.4996\pm 0.0295,0.5054\pm 0.0330\\}$ for $N=1-6$,
which coincides with the results by sinusoidal fitting very well and all
beating the SQL.

##  Appendix C Derivation of the estimation sensitivity in noise scenarios

In this section, we aims to provide a general expressions on the frequency
estimation sensitivity under the dephasing dynamics, including both the
product state and GHZ state,and in the Markovoian ($\gamma(t)=\gamma_{M}t$)
and non-Markovian case ($\gamma(t)=\gamma_{N}t^{2}$).

We start from the measurement operator $P_{x}=\sigma_{x}^{\otimes N}$ for
$N-$qubit GHZ state (the N-qubit product state can be calculated with single
qubit operator, but with N copies.). The mean value $\langle P_{x}\rangle$,
uncertainty $\Delta^{2}P_{x}$ and $\frac{\partial P_{x}}{\partial\omega}$ is
respectively represented as

$\displaystyle\langle P_{x}\rangle$ $\displaystyle=$ $\displaystyle
e^{-N\gamma(t)}\mathrm{cos}(N\omega t)$ (8) $\displaystyle\Delta^{2}P_{x}$
$\displaystyle=$ $\displaystyle\langle P_{x}^{2}\rangle-\langle
P_{x}\rangle^{2}=1-e^{-2N\gamma(t)}\mathrm{cos}^{2}(N\omega t)$ (9)
$\displaystyle\frac{\partial P_{x}}{\partial\omega}$ $\displaystyle=$
$\displaystyle Nte^{-N\gamma(t)}\mathrm{sin}(N\omega t)$ (10)

With a total available time resource $T$, it is possible to repeat the
$\upsilon=\frac{T}{t}$ runs of experiment. Hence For the N-qubit GHZ state,
the sensitivity of frequency estimation is calculated as

$\displaystyle\Delta^{2}\omega_{GHZ}$
$\displaystyle=\frac{\left(\Delta^{2}P_{x}\right)/\upsilon}{\left|\partial\left\langle
P_{x}\right\rangle/\partial\omega\right|^{2}}$ (11)
$\displaystyle=\frac{1-e^{-2N\gamma(t)}\mathrm{cos}^{2}(N\omega
t)}{N^{2}Tte^{-2N\gamma(t)}\mathrm{sin}^{2}(N\omega t)}$

As for the N-qubit product state, it can be treated as repeating N runs of
single-qubit experiment within time t, thus for time resource T, the total run
of single qubit experiment is $\upsilon=N\frac{T}{t}$, and the sensitivity is

$\Delta^{2}\omega_{product}=\frac{1-e^{-2\gamma(t)}\mathrm{cos}^{2}(\omega
t)}{NTte^{-2\gamma(t)}\mathrm{sin}^{2}(\omega t)}$ (12)

Considering the optimal condition of interrogation time, that is

$\displaystyle 2Nt\frac{d\gamma\left(t\right)}{dt}=1$ (13) $\displaystyle
N\omega t=\frac{k\pi}{2},k\;is\;odd$ (14)

(1)Markovian case. In this case, we consider the semigroup dynamics
$\gamma(t)=\gamma_{M}t$ raised in the original theorem paper [23, 24], where
$\gamma_{M}$ is constant factor.

For N-qubit GHZ state, the optimal time can be obtained to be
$t_{e}=\frac{1}{2N\gamma_{M}}$. For product state, the optimal time is
$t_{p}=\frac{1}{2\gamma_{M}}$. By substituting the optimal time and eq. 14
into eq.11 and eq.12 respectively, we get the ultimate expression of
sensitivity of GHZ state and product state

$\Delta^{2}\omega_{GHZ}=\Delta^{2}\omega_{product}=\frac{2e\gamma_{M}}{NT}\\\
$ (15)

(1)non-Markovian case. We consider the quadratic decay behavior
$\gamma(t)=\gamma_{N}t^{2}$ which has quantum Zeno effect in initial short
time scale. For N-qubit GHZ state, the optimal time is
$t_{e}=\sqrt{\frac{1}{4N\gamma_{N}}}$. For product state, the optimal time is
$t_{p}=\sqrt{\frac{1}{4\gamma_{N}}}$. In this case, sensitivity of GHZ state
and product become different

$\displaystyle\Delta^{2}\omega_{GHZ}$
$\displaystyle=\frac{2(e\gamma_{N})^{0.5}}{N^{\frac{3}{2}}T}$ (16)
$\displaystyle\Delta^{2}\omega_{product}$
$\displaystyle=\frac{2(e\gamma_{N})^{0.5}}{NT}$

##  Appendix D Comparison of quantum metrology in non-Markovian environment
with Markovian environment

We have demonstrated surpassing the SQL in parallel noise with quadratic-like
decay of non-Markovian circumstance. Entanglement is commonly recognized as a
central part to this task. But entanglement is not the only ingredient
responsible to the outperformance. It is still interesting to investigate the
role of non-Markovianity. As a compliment to our experiment, we compare the
performance of entangled probes in non-Markovian and Markovian dephasing
cases.

In the main text, we performed the non-Markovian case with $\gamma(t)=t^{2}$,
here the pure Markovian dephasing where the exponential decay
$\gamma(t)=e^{-0.5}t$. These two cases exhibit the same precision with $N=1$
but differ as the particle number increasing. For simulation of Markovian
dephasing dynamics, the BD pairs is replaced by the wave-plates which is used
to introduce the phase-flipped operation. The Markovian dephasing dynamics can
be experimentally engineered by a proper mixture of a pure initial state and
its phase-fliped state with appropriate factions of total measurement time,
then tracing out the classical time information about which state is prepared.
Such a method is generally used in optical channel simulation [45].

Figure 5:  Relative resolution of non-Markovian over Markovian case. The $r=1$
means there is no relative advantages for non-Markovian environment, which is
the case when N=1.

We define the relative resolution of non-Markovian over Markovian case as

$r^{2}=\frac{\left|1/\triangle^{2}\omega\right|_{NM}}{\left|1/\triangle^{2}\omega\right|_{M}}=N\left(\frac{t_{NM}}{t_{M}}\right)e^{2\gamma\left(t_{M}\right)-2N\gamma\left(t_{NM}\right)}$
(17)

Here the subscript $NM\left(M\right)$ denotes the non-Markoivan (Markovian)
case and the interrogation time is optimized according to eq.13. Fig. depicts
the experimental result of relative resolution of GHZ state with $N$ ranging
from 1 to 6, which accord with the Zeno limit $r^{2}=1/\sqrt{N}$ intermediate
with SQL and HL. The reason is that in the ideal case, that is, perfect GHZ
probes preparation, the GHZ state in non-Markovian dephasing is an alternative
to the product state in Markovian dephasing because of the same sensitivity.
Thus, comparision with the these two cases also to some degree reflects the
Zeno scaling, where the preparation imperfection of experiment could be
justifiably excluded. It is worth noting that for the specific two fixed
Markovian and non-Markovian environment, even if they shows the same precision
in case of $n_{0}$\- qubit probes, when moving toward higher qubit $N>n_{0}$,
the non-Markovian one will show the advantages over Markovian one.

##  Appendix E Numerical analysis with state preparation noise

It is a common issue that performance of quantum tasks will degrade with the
increasing noise. The preparation imperfection is one of the inherent noise.
Generally, preparation of entangled state is based on fusing different
particles, which make preparation noise greatly increased with the entangled
particle number scaled due to the increasing circuit depth. In this section,
we will briefly analysis a realistic scenario where the preparation noise is
scaled as additional qubit is incorporated, and calculate the performance of
quantum metrology in non-Markovian dephasing dynamics.

Figure 6:  Numerical analyasis of relations of the sensitivity with respect to
qubit number N up to $10^{3}$. The upper and down shaded areas represent the
SQL and HL respectively.

For the SPDC photons, extending the entangled number of particles by two
requires one fusion gate, thus it is reasonable to model the visibility of
prepared state with a exponentially decay with numbers of fusion gate. We
consider the white noise for simplicity

$\rho_{noise}=v^{N/2}|\mathrm{GHZ}\rangle\langle\mathrm{GHZ}|_{N}+\frac{1-v^{N/2}}{2^{N}}\mathcal{I}$
(18)

where the $|\mathrm{GHZ}>=(|0\rangle^{\otimes N}+|1\rangle^{\otimes
N})/\sqrt{2}$ and $\mathcal{I}$ is white noise. The visibility for N-qubit GHZ
state is $v^{N/2}$. In Fig. 6, we numerically calculate the performance of
quantum metrology with respect to the particle number, under the various
condition of visibility. It is immediately clear that any small imperfection
of fusion leading to imperfect visibility will eventually destroy the
advantages of superclassical prevision when the N is sufficient large.
However, the SQL can be surpassed when in moderate mount of qubit number and
visibility imperfection, which is within the reach of current quantum
technology. Overcoming the imperfection accumulation as the circuit depth
increasing is a notoriously difficult in quantum technology. In the future, A
through investigation of non-Markovianity and accompanying method to take use
of the non-Markovian features to reduce the detrimental effect of noise is
expected to applied on the quantum metrology.


:
1 2018 AutoML 2018

# Towards AutoML in the presence of Drift: first results

Jorge G. Madrid<EMAIL_ADDRESS>
INAOE  Mexico
Hugo Jair Escalante<EMAIL_ADDRESS>
INAOE  Mexico
Eduardo F. Morales<EMAIL_ADDRESS>
INAOE  Mexico
Wei-Wei Tu<EMAIL_ADDRESS>
4Paradigm Inc  China
Yang Yu<EMAIL_ADDRESS>
Nanjing University  China
Lisheng Sun-Hosoya<EMAIL_ADDRESS>
UPSud  U. Paris-Saclay  France
Isabelle Guyon<EMAIL_ADDRESS>
UPSud/INRIA  U. Paris-Saclay  France and ChaLearn  USA
Michele Sebag<EMAIL_ADDRESS>
CNRS  U. Paris-Saclay  France

###### Abstract

Research progress in AutoML has lead to state of the art solutions that can
cope quite well with supervised learning task, e.g., classification with
AutoSklearn. However, so far these systems do not take into account the
changing nature of evolving data over time (i.e., they still assume i.i.d.
data); even when this sort of domains are increasingly available in real
applications (e.g., spam filtering, user preferences, etc.). We describe a
first attempt to develop an AutoML solution for scenarios in which data
distribution changes relatively slowly over time and in which the problem is
approached in a lifelong learning setting. We extend Auto-Sklearn with sound
and intuitive mechanisms that allow it to cope with this sort of problems. The
extended Auto-Sklearn is combined with concept drift detection techniques that
allow it to automatically determine when the initial models have to be
adapted. We report experimental results in benchmark data from AutoML
competitions that adhere to this scenario. Results demonstrate the
effectiveness of the proposed methodology.

###### keywords:

AutoML, Life Long Machine Learning, Concept Drift, AutoSKLearn,

##  1 Introduction

Autonomous Machine Learning (AutoML) is the field focusing on methods that aim
at automating different stages of the machine learning process. AutoML
solutions are increasingly receiving more attention from both the ML community
and users because of (1) the large amounts of data readily available
everywhere, and (2) the lack of domain and/or ML experts who can
advise/supervise the development of ML-based systems.

Although progress in AutoML is vast, the considered scenarios are somewhat
constrained, e.g., in the type of approached problem, in the assumptions on
data, in the size of datasets, etc. In this context, one of the most desirable
features for AutoML methods is to work under a _lifelong machine learning_
(LML) setting. LML refers to systems that can sequentially learn many tasks
from one or more domains in its lifetime (Silver and amd Lianghao Li, 2013),
these systems (not restricted to supervised learning) require the ability to
retain knowledge, adapt to changes and transfer knowledge when learning a new
task. An AutoML method that learns from different tasks and that is able to
adapt itself during its lifetime would comprise a competitive and robust all-
problem machine learning solution.

This paper aims at exploring the viability of AutoML methods to operate in a
LML setting, in particular in a scenario where the targets evolve over time,
that is, in the presence of concept drift. We modify the Auto-Sklearn method
with mechanisms that allow it to deal with the drift phenomenon in a
simplified LML evaluation scenario. The proposed mechanisms are sound and
highly intuitive, yet very useful. We perform experiments in benchmark data
from concept drift and AutoML with drift. Experimental results reveal that the
proposed mechanisms allow Auto-Sklearn to successfully cope with drift. To the
best of our knowledge these are the first results reported on AutoML for a
simplified LML scenario in the presence of concept drift111One should note
that our work is different from standard data-stream / concept drift learning
methods in the sense that in AutoML we aim to autonomously find preprocessing,
feature selection and classification methods (together with hyper parameter
optimization), while in most of the existing literature the problem is reduced
to modify the classification model. .

##  2 Related work

Although the term ‘AutoML’ was coined recently by F. Hutter and collaborators
(Thornton et al., 2013; Hutter, 2009), the problem of hyper-parameter
selection has been studied for several decades in the machine learning
community (Bozdogan, 1987; Bengio, 2000; Bergstra et al., 2011; Bergstra and
Bengio, 2012). However, the original emphasis was on over-fitting avoidance
while, with the emergence of “big data” the current emphasis is on search
efficiency. Novel effective approaches have been proposed in the academic
literature that have become wide spread among practitioners because they are
both theoretically well founded and practically efficient: (1) Bayesian
Optimization (BO) methods build a posterior $p(model|data)$ by applying
candidate models to the input data and use this posterior distribution to
guide the search (e.g. (Hutter et al., 2011; Swersky et al., 2014)). (2)
Complementary to BO, Meta Learning develops a set of meta-features capturing
the nature of data, which are then used to infer the model performance based
on past experiences on similar data, without actually training the model (e.g.
(Muñoz et al., 2018)). (3) Evolutionary Algorithms (EA) learn a distribution
over hyper-parameters and updates it to help the search (e.g. (Real et al.,
2017)). (4) Reinforcement learning approaches (RL), where the hyper-parameter
optimization problem is formulated as learning an efficient policy to move in
the hyper-parameter space and solved using RL techniques (e.g. (Zoph and Le,
2016; Baker et al., 2016)). The algorithm Auto-sklearn used in this paper is
based on a BO approach initialized with Meta Learning.

Hyper-parameter selection usually focuses on solving tasks in isolation, but,
if tasks show some sequential dependency, a lifelong learning (LML) approach
can be applied to continuously retain and immigrate knowledge across tasks and
make the future learning more efficient. The concept of LML was first
introduced in robot control (Thrun and Mitchell, 1995), where, inspired by the
fact that a robot might be exposed to various learning tasks during their
lifetime and the knowledge learned might be transfered to make future learning
more efficient, they proposed EBNN (explanation-based neural network): suppose
the robot perform all tasks in the same environment (e.g. housekeeping robot),
then its knowledge about the environment (called action model, the mapping
between state-action pairs to the next state) can be transfered to new task
using back-propagation. Since then, diverse techniques have been developed in
lifelong supervised learning (Silver and Mercer, 2002, 1996, 2001; Chen et
al., 2018; Fei et al., 2016).

Due to the big volume of data being constantly generated, many prediction
problems need a model that continuously receives data and thus cannot work in
an off-line/static mode with historical data. Some of these environments are
non-stationary where data distributions change over time, this phenomenon is
known as concept drift (Schlimmer and Granger, 1986; Widmer and Kubat, 1996;
Gama et al., 2014). Numerous research work have been done for adapting models
to data streams with presence of concept drift. Hulten et al. (2001) developed
CVFDT where a Decision Tree is maintained up-to-date with regard to a sliding
window of examples: an alternative sub-tree is built when drift is detected in
the window, and is used to replace the old sub-tree when this new one becomes
more performing. Then, by proving the out-performance of ensembling compared
to single classifiers in the concept drift environment, Wang et al. (2003b)
proposed weighted classifier ensemble, where adaptation is done by dynamically
updating the weight for each base classifier according to its expected
prediction accuracy on current test stream. To address the problem of sliding
window size, Bifet and Gavalda (2007) introduced Adwin in which the window is
resized based on changing rate observed in the window, Adwin is also used
widely as a change detector as in Bifet et al. (2010) and van Rijn et al.
(2014). The same authors then came up with Leverage Bagging (Bifet et al.
(2010)) where examples are weighted by a well parameterized Poisson
distribution to add randomization in input data that improve the accuracy of
ensembling. van Rijn et al. (2014), Rossi et al. (2014) and van Rijn et al.
(2015) collaborated meta-learning techniques to solve the algorithm selection
problem: predict best model for next upcoming stream based on meta-knowledge
collected from previous streams.

Although work for processing streams and data in the presence of drift is
vast, to the best of our knowledge existing work as not approaching the AutoML
setting: automatically building and updating a _full model_ (Escalante et al.,
2009), that is a model that comprises data preprocessing, feature selection
and classification model and that optimizes hyperparameters of the whole
model.

In the scenario of LML-AutoML, the learning algorithm should be able to
incorporate new data and update previous predictive models. In this paper, we
follow the 3 steps of on-line adaptive learning procedure proposed in (Gama et
al., 2014): (1)Predict. When new example $X_{t}$ arrives, a prediction
$\hat{y}ˆt$ is made using the current model $L_{t}$. (2)Diagnose. After some
time the true label $y_{t}$ is received and the loss can be estimated as
$f(\hat{y}_{t},y_{t})$, and (3)Update. use the example $(X_{t},y_{t})$ to
update the model to obtain $L_{t+1}$. Several methods that cope with concept
drift use an explicit drift detection algorithm (Wang et al., 2003a; Beyene et
al., 2015; Street and Kim, 2001). One of the most used detector which is used
as a benchmark in new detection methods is the Drift Detection Method (DDM)
(Gama et al., 2004). It is a method that controls the trace of the on-line
error by modeling the classification errors with a Binomial distribution. Some
extensions to DDM have been developed to improve its performance. Fast
Hoeffding Drift Detection Method (FHDDM) (Pesaranghader and Viktor, 2016) uses
a sliding window and Hoeffding’s inequality to detect drifting points earlier,
experimental results also show that the number of false positive and false
negatives is minor (Pesaranghader and Viktor, 2016; Pesaranghader et al.,
2017). Other methods extend FHDDM, however, these require additional
parameters.

##  3 AutoML scenario and proposed methods

As previously mentioned we consider a simplified LML - AutoML with a concept
drift scenario, which is precisely the scenario considered in the forthcoming
AutoML3222https://www.4paradigm.com/competition/nips2018 challenge. The aim is
assessing the robustness of methods to concept drift and its lifelong learning
capabilities. It is assumed that there is an initial training (labeled)
dataset available, and multiple batches of test data. Also, we assume that
data are temporally dependent and are subject to an underlying form of the
concept drift phenomenon. For the LML - AutoML evaluation, datasets will be
split into sequential batches so that the lifelong scenarios can be evaluated:
the test data will come in the form of sequential batches of data, each batch
needs to be predicted at first, then the target values will be revealed and
thus become a batch of new training data. From the model predictions and the
revealed target values of a specific test batch, its performance can be
evaluated. The performance of the model is given by taking the average across
batches. Figure 1 illustrates the considered scenario.

Figure 1: Evaluation scenario considered in the AutoML3 challenge.

###  3.1 Auto-sklearn

Auto-sklearn is an AutoML solution that has succeed in recent academic
competitions (Feurer et al., 2015; Guyon et al., 2016, 2015). In our opinion,
it is THE state of the art on AutoML and for that reason we considered it for
our study. Auto-Skelearn is implemented in scikit-learn (Pedregosa et al.,
2011), it initially comprised 15 classification algorithms, 14 preprocessing
methods, and 4 data preprocessing methods. Similarly to Auto-WEKA (Thornton et
al., 2013), Feurer et al. approach AutoML as a Combined Algorithm Selection
and Hyper-parameter (CASH) or full model selection problem (Feurer et al.,
2015; Escalante et al., 2009), which they tackle using SMAC, a three-based
Bayesian optimization method. There are two key components that make Auto-
Sklearn so competitive. The first is based on meta-learning, complementary to
Bayesian optimization, it is used to warmstart the optimization by quickly
suggesting instantiations of a framework that are likely to perform well. The
meta-learning was done in an off-line phase where 38 meta-features were
learned from 140 OpenML datasets (Vanschoren et al., 2014). The second feature
is the automated ensemble construction of models evaluated during
optimization, when finding the best model instead of discarding the rest of
the models found in the Bayesian optimization process, Feurer, et. al. store
them and then build and ensemble using a greedy ensemble selection algorithm.

###  3.2 Proposed method

Auto-Sklearn was modified with basic mechanisms for allowing it to cope with
incoming data as depicted in Figure 1. The overall proposed procedure is shown
in Algorithm 1. With a first batch, an initial ensemble model is learned by
using Auto-Sklearn. With the generated model predictions are made for the next
batch. After the predictions are made, feedback for this batch is received
(i.e., ground truth), using a drift detector these predictions are diagnosed
to determine if drift has happened. If the detector triggers the drift alarm,
the current ensemble model is adapted by using one of the mechanisms described
below. After this, the system receives the next batch and the process is
repeated until no batches are left. In the rest of this section we describe
the components of the proposed method, namely: the drift detector and the
proposed adaptation mechanisms.

Data: $D(X,y)$ examples

Take a batch $D^{\prime}_{t}$ of size n,
$D^{\prime}_{t}(X^{\prime},y^{\prime})\in D(X,y)$;;

$T_{t}\leftarrow$ learn a model with auto-sklearn using $D^{\prime}_{t}$;

while  _there is data in D_ do

Take next batch $D^{\prime}_{t+1}$;;

$\hat{y}\leftarrow$ Make predictions with $T_{t}$;;

for  _$y_{j}\in\hat{y}$_ do

drift_detected = Detector($y_{j}==y^{\prime}_{j}\in y^{\prime}$);

//drift will be detected with model performance

end for

if  _drif_detected_ then

$T_{t+1}=adapt(T,D^{\prime}_{t+1})$;;

Detector.reset();;

$t=t+1$

else

$T_{t+1}=T_{t}$;;

$t=t+1$

end if

end while

Algorithm 1 Drift adaption schema for Auto-sklearn

####  3.2.1 Drift detector

In a strict LML - AutoML context, where no human intervention is expected,
selecting a drift detection algorithm is not trivial, different methods
perform differently depending on the type of drift in the data: incremental,
abrupt, reoccurring, gradual. Some of these methods also require parameter
tuning to achieve better results. For this experiment, we decided to use a
particular drift detector with default hyper-parameters to make the problem
more manageable and postpone to future work the automatic selection of this
type of models. Specifically, the Fast Hoeffding Drift Detection Method
(FHDDM) method was selected because according to experiments in (Pesaranghader
et al., 2017) it was found that in many datasets its performance can be
compared to the state-of-the-art. The implementation of FHDDM in Tornado
(Pesaranghader et al., 2017) was integrated with AutoSKlearn.

####  3.2.2 Model adaptation methods

Three approaches were implemented for adapting the model generated by Auto-
Sklearn, a global replacement strategy where the initial model found by Auto-
Sklearn is retrained with new examples and two variants of model management
strategies.

Model replacement. A traditional concept drift adaptation where the model is
globally replaced with a new one. Taking advantage of the Auto-Sklearn
improvements, the model is not trained from scratch. Having the meta-features
learned with the meta-learning process from Auto-Sklearn, these are used for
the creation of the new model, which is a new ensemble with the best models
found by the SMAC process, the learning for the experimentation was performed
storing all data received instead of only the current batch.

Model management. Two variants of this formulation were considered. The first
strategy assumes the data is generated by a mixture distribution (that formed
by previous batches and the current one) and the ensemble weights from the
initially learned ensemble are updated with new data, either: (1) using the
latest batch or (2) using all the stored data up to the current batch, we call
these variants WU-latest and WU-all, respectively. Creators of AutoSKlearn
(Feurer et al., 2015) found that uniformly weighted ensembles did not work
well. Instead, a greedy ensemble selection algorithm was used to build the
ensemble. Such same algorithm is used in this work to update the weights of
each model under the model management variants. With the new data every model
performance is computed again and the ensemble is rebuild with new
information.

In a second model management variant called _Add New_ , new models are learned
with all the stored data, meta-learning process is also skipped in this case,
and using auto-sklearn ensemble construction methods these new models are
integrated in the initial ensemble. However, the implementation of this last
strategy did not work as expected since the original design of auto-sklearn
does not consider adding new models to the ensemble so a new model selection
algorithm for the ensemble construction ought to be implemented.

##  4 Experiments and results

###  4.1 Data

For the empirical evaluation we used benchmark data form both concept drift
and the AutoML fields, where the AutoML data sets considered are known to
incorporate temporal dependencies across instances. The considered data sets
are described in Table LABEL:tab:datasets.

tab:datasets

Table 1: Datasets considered for experimentation.

Concept drift datasets
---
Dataset | instances | attributes | Reference
Chess | 503 | 8 | (Žliobaite, 2010)
Poker | 100,000 | 10 | (Olorunnimbe et al., 2015)
Electricity | 45,312 | 8 | (Baena-García et al., 2006)
Stagger | 70,000 | 3 | (Gama et al., 2014)
AutoML2 challenge data sets
Dataset | instances | attributes | Reference
PM | 49,964 | 89 | (Guyon et al., 2018)
RH | 60,042 | 76 | (Guyon et al., 2018)
RI | 57,306 | 113 | (Guyon et al., 2018)
RL | 56,209 | 22 | (Guyon et al., 2018)
RM | 55,239 | 89 | (Guyon et al., 2018)

Concept drift data sets have been widely used for the evaluation of drift
detection techniques. _Chess_ comprises 2 years of chess games collected from
chess.com, the task is to predict whether a player will win or lose a match
given players and game setup features, the player increases its abilities
through time and faces more skilled players, this is where the concept drift
is expected. In the _Poker_ dataset each instance is an example of a hand
having five playing cards drawn from a standard deck. Each card is described
by two attributes (suit and rank) for a total of ten attributes. The class
predicts the poker hand, 10 classes are considered. Since the poker hands were
generated in order (varying suits and ranks in order), the concept drifts
multiple times. The _electricity_ market dataset was collected from the
Australian New South Wales Electricity Market. Each instance represents the
market state in a period of 30 minutes. The task in this dataset is to predict
if the market prices are going up or down for the next period of time.
Finally, a synthetic Stagger dataset was generated to test the methods, three
drift points are artificially induced were the concept changes abruptly.
According to previous work, we used accuracy as evaluation measure for these
datasets.

AutoML data sets comprise undisclosed data from click user data, these
datasets were used in the AutoML2 challenge (Guyon et al., 2018). Although the
data has been keep confidential, it is known that there is a temporal
dependency across instances. We expect the proposed methods to capture these
dependencies and improve the performance of a straightforward AutoML
technique. We know _RH_ and _RI_ were collected from applications in startup
phase, and behavior changed dramatically during that time. _RL_ was collected
from content recommendation applications, the items were user generated
contents, there were a certain proportion of new contents generated each day,
the user preferences of the items were changed along time. _PM_ and _RM_ were
collected from a mature recommender system in different time periods, the
items were cars, the candidate set of cars was relatively stable along time,
the user preferences were also relatively stable compared to other datasets.
For these datasets we used the normalized area under the ROC curve as
evaluation measure.

###  4.2 Results

For each of the considered datasets the following setup was considered.
Training partitions were used to obtain an AutoSKlearn model. For concept
drift datasets, the data was divided into batches of equal size, and the first
batch was used as training set. For the AutoML datasets the predefined
training partitions were used for generating the initial model. After that,
the test set was processed in batches. The actual model was used to predict
labels for the batch $t$ and performance was estimated, after that, test
labels for this batch were made available to the method. Then we applied the
drift detector. If drift was detected, the methods described in Section 3 were
applied to adapt the current model, which was then used for batch $t+1$. In
experiments, we compare the performance of the initial AutoSKlearn model
(_Base_) with the replacement, WU-all, WU-batch and the Add New methods.

Table LABEL:tab:benchmark reports the average (across batches) performance for
the concept drift datasets. Regarding the real datasets, in all but one
configuration (_Poker_ dataset with WU-latest method) the drift aware AutoML
solutions outperformed the base model. As it can be expected, replacing the
initial model with a new model obtained by applying AutoSKlearn with all
available data obtained the best performance. Model replacement, however, is
the most computationally expensive solution. A competitive alternative is the
WU-all method, in which ensemble weights are updated by using all of the
available data. In our experiments, WU-all method was in the worse case about
5 times faster than the replacement technique. The speedup was more noticeable
in large datasets.

Interestingly, most drift aware methods failed with the synthetic data set
(_Stagger_), this was due in part to the abrupt drift present in data:
synthetic drift is simulated by inverting the concept (negative instances are
considered as positive ones). WU-all and WU-latest models only consider models
built before the drift (i.e. with the rule before the drift) and thus fail to
classify correctly after drift detected. The Add new method also tries to
incrementally adjust to changes, but AutoSKlearn fails to find an ensemble
that classifies correctly both instances before and after the drift. On the
other hand, the replacement method builds models from scratch after drift is
detected and is able to improve the accuracy of the ensemble.

tab:benchmark  Method Electricity Poker Chess Stagger Rank Base 67.15 67.97
38.23 54.09 4.5 Replacement 76.44 90.38 58.13 78.81 1 WU-all 70.23 76.89 52.62
54.09 2.75 WU-latest 67.95 67.49 53.24 54.09 3.5 Add new model 67.47 74.98
47.28 54.14 3.25

Table 2: Results on benchmark data.

Figure LABEL:fig:B shows the per-batch improvement of AutoML drift aware
methods vs. using the initial model. The figure shows a somewhat erratic
behavior at times, although, in general, these plots confirm the results
presented in Table LABEL:tab:benchmark. It can be seen from these plots that
the WU-batch method is very sensitive to the batch used to adjust weights (see
rightmost top plot). The Replacement and WU-all strategy consistently
outperform the base model in the real data sets, and for the synthetic dataset
(rightmost bottom) all methods but replacement perform poorly.

fig:B

Figure 2: Performance of drift aware AutoML variants. From top to bottom and
left to right results for: Electricity, Poker, Chess and Stagger are shown,
respectively.

Table LABEL:tab:automl2 shows the results obtained in the AutoML2 challenge
data sets, performance is reported in terms of the normalized AUC. For _PM_
and _RM_ datasets the drift detector did not detect drift in any batch, and
therefore the base model was used for making predictions in all the batches.
This could be due to the maturity of the application from which _PM_ and _RM_
were collected from. The drift of concept evolves slowly and it cannot be
captured by the batch size. On the other hand, for datasets collected from
startup businesses or UGC recommender systems, due to the changing nature of
the applications, for _RH, RI_ and _RL_ , at least one of the adaptive AutoML
methods outperformed considerably the base performance. For _RL_ , the
Replacement method improved relatively the performance of the base model by
47%. For _RI_ the WU-latest method improved the initial performance by more
than 60%. Whereas for _RH_ all of the adaptive AutoML variants outperformed
the reference performance; the highest relative improvement being of 73%
obtained by the WU-all strategy.

tab:automl2  Method PM∗ RH RI RL RM∗ Base 0.433 0.192 0.299 0.340 0.264
Replacement 0.433 0.197 0.092 0.478 0.264 WU-all 0.433 0.370 0.199 0.212 0.264
WU-latest 0.433 0.270 0.450 0.405 0.264 Add new 0.433 0.298 0.184 0.277 0.264

Table 3: Results on data from the AutoML2 challenge.

Although more experiments are needed, the results in AutoML2 data
suggest/confirm that each dataset presents a different variant of the concept
drift phenomenon. _RL_ seems to follow the behavior of datasets in Table
LABEL:tab:benchmark. _RH_ seems to exhibit a slowly progressing drift, where
WU-all takes advantage. While _RI_ seems to show a drift aligned with the
concept drift detector (hence the WU-latest method is able to find quite
useful weights).

##  5 Conclusions

AutoML is an increasingly trending topic because of its relevance given the
amount of data being generated nowadays. Although very effective AutoML
methods have been proposed so far, to the best of our knowledge all of them
focus on the assumption of static (iid) data. However, on-line data is
constantly changing and therefore, static solutions may not be useful for
evolving data streams. This paper described preliminary experimentation on the
evaluation of the drift adaptive capabilities of a state of the art AutoML
solution. To the best of our knowledge this is the first work dealing with
AutoML in the presence of drift. Experimental results in benchmark data
confirm the usefulness of the proposed mechanisms for dealing with drift.
Although our results are far from being conclusive, they bring some light into
the performance of AutoML for evolving data streams.

## References

  * Baena-García et al. (2006) Manuel Baena-García, José del Campo-Ávila, Raúl Fidalgo, Albert Bifet, Ricard Gavaldà, and Rafael Morales-Bueno.  Early drift detection method.  2006\.
  * Baker et al. (2016) Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar.  Designing neural network architectures using reinforcement learning.  _arXiv preprint arXiv:1611.02167_ , 2016.
  * Bengio (2000) Yoshua Bengio.  Gradient-based optimization of hyperparameters.  _Neural computation_ , 12(8):1889–1900, 2000\.
  * Bergstra and Bengio (2012) James Bergstra and Yoshua Bengio.  Random search for hyper-parameter optimization.  _Journal of Machine Learning Research_ , 13(Feb):281–305, 2012.
  * Bergstra et al. (2011) James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl.  Algorithms for hyper-parameter optimization.  In _Advances in neural information processing systems_ , pages 2546–2554, 2011.
  * Beyene et al. (2015) Ayne A. Beyene, Tewelle Welemariam, Marie Persson, and Niklas Lavesson.  Improved concept drift handling in surgery prediction and other applications.  _Knowl. Inf. Syst._ , 44(1):177–196, July 2015\.  ISSN 0219-1377.  10.1007/s10115-014-0756-9.  URL http://dx.doi.org/10.1007/s10115-014-0756-9.
  * Bifet and Gavalda (2007) Albert Bifet and Ricard Gavalda.  Learning from time-changing data with adaptive windowing.  In _Proceedings of the 2007 SIAM international conference on data mining_ , pages 443–448. SIAM, 2007.
  * Bifet et al. (2010) Albert Bifet, Geoff Holmes, and Bernhard Pfahringer.  Leveraging bagging for evolving data streams.  In _Joint European conference on machine learning and knowledge discovery in databases_ , pages 135–150. Springer, 2010.
  * Bozdogan (1987) Hamparsum Bozdogan.  Model selection and akaike’s information criterion (aic): The general theory and its analytical extensions.  _Psychometrika_ , 52(3):345–370, 1987.
  * Chen et al. (2018) Zhiyuan Chen, Nianzu Ma, and Bing Liu.  Lifelong learning for sentiment classification.  _arXiv preprint arXiv:1801.02808_ , 2018.
  * Escalante et al. (2009) Hugo Jair Escalante, Manuel Montes, and Luis Enrique Sucar.  Particle swarm model selection.  _J. Mach. Learn. Res._ , 10:405–440, June 2009.  ISSN 1532-4435.  URL http://dl.acm.org/citation.cfm?id=1577069.1577084.
  * Fei et al. (2016) Geli Fei, Shuai Wang, and Bing Liu.  Learning cumulatively to become more knowledgeable.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 1565–1574. ACM, 2016.
  * Feurer et al. (2015) Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Springenberg, Manuel Blum, and Frank Hutter.  Efficient and robust automated machine learning.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems 28_ , pages 2962–2970. Curran Associates, Inc., 2015.  URL http://papers.nips.cc/paper/5872-efficient-and-robust-automated-machine-learning.pdf.
  * Gama et al. (2014) João Gama, Indrė Žliobaitė, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia.  A survey on concept drift adaptation.  _ACM Comput. Surv._ , 46(4):44:1–44:37, March 2014.  ISSN 0360-0300.  10.1145/2523813.  URL http://doi.acm.org/10.1145/2523813.
  * Gama et al. (2004) João Gama, Pedro Medas, Gladys Castillo, and Pedro Rodrigues.  Learning with drift detection.  In Ana L. C. Bazzan and Sofiane Labidi, editors, _Advances in Artificial Intelligence – SBIA 2004_ , pages 286–295, Berlin, Heidelberg, 2004\. Springer Berlin Heidelberg.
  * Guyon et al. (2015) Isabelle Guyon, Kristin Bennett, Gavin C. Cawley, Hugo Jair Escalante, Sergio Escalera, Tin Kam Ho, Núria Macià, Bisakha Ray, Mehreen Saeed, Alexander R. Statnikov, and Evelyne Viegas.  Design of the 2015 chalearn automl challenge.  In _2015 International Joint Conference on Neural Networks, IJCNN 2015, Killarney, Ireland, July 12-17, 2015_ Guyon et al. (2015), pages 1–8.  10.1109/IJCNN.2015.7280767.  URL https://doi.org/10.1109/IJCNN.2015.7280767.
  * Guyon et al. (2016) Isabelle Guyon, Imad Chaabane, Hugo Jair Escalante, Sergio Escalera, Damir Jajetic, James Robert Lloyd, Núria Macià, Bisakha Ray, Lukasz Romaszko, Michèle Sebag, Alexander R. Statnikov, Sébastien Treguer, and Evelyne Viegas.  A brief review of the chalearn automl challenge: Any-time any-dataset learning without human intervention.  In _Proceedings of the 2016 Workshop on Automatic Machine Learning, AutoML 2016, co-located with 33rd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 24, 2016_ , pages 21–30, 2016.  URL http://jmlr.org/proceedings/papers/v64/guyon_review_2016.html.
  * Guyon et al. (2018) Isabelle Guyon, Lisheng Sun-Hosoya, Marc Boullé, Hugo Jair Escalante, Sergio Escalera, Zhengying Liu, Damir Jajetic, Bisakha Ray, Mehreen Saeed, Michele Sebag, Alexander Statnikov, Wei-Wei Tu, and Evelyne Viegas.  Analysis of the automl challenge series 2015-2018.  In Frank Hutter et al., editor, _AutoML, Springer Series on Challenges in Machine Learning (to appear)_. 2018.
  * Hulten et al. (2001) Geoff Hulten, Laurie Spencer, and Pedro Domingos.  Mining time-changing data streams.  In _Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 97–106. ACM, 2001.
  * Hutter (2009) Frank Hutter.  _Automated configuration of algorithms for solving hard computational problems_.  PhD thesis, University of British Columbia, 2009.
  * Hutter et al. (2011) Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown.  Sequential model-based optimization for general algorithm configuration.  In _International Conference on Learning and Intelligent Optimization_ , pages 507–523. Springer, 2011.
  * Muñoz et al. (2018) Mario A Muñoz, Laura Villanova, Davaatseren Baatar, and Kate Smith-Miles.  Instance spaces for machine learning classification.  _Machine Learning_ , 107(1):109–147, 2018.
  * Olorunnimbe et al. (2015) M Kehinde Olorunnimbe, Herna L Viktor, and Eric Paquet.  Intelligent adaptive ensembles for data stream mining: a high return on investment approach.  In _International Workshop on New Frontiers in Mining Complex Patterns_ , pages 61–75. Springer, 2015.
  * Pedregosa et al. (2011) Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake VanderPlas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay.  Scikit-learn: Machine learning in python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.  URL http://dl.acm.org/citation.cfm?id=2078195.
  * Pesaranghader and Viktor (2016) Ali Pesaranghader and Herna L. Viktor.  Fast hoeffding drift detection method for evolving data streams.  In Paolo Frasconi, Niels Landwehr, Giuseppe Manco, and Jilles Vreeken, editors, _Machine Learning and Knowledge Discovery in Databases_ , pages 96–111, Cham, 2016. Springer International Publishing.
  * Pesaranghader et al. (2017) Ali Pesaranghader, Herna Viktor, and Eric Paquet.  Reservoir of diverse adaptive learners and stacking fast hoeffding drift detection methods for evolving data streams.  _CoRR_ , abs/1709.02457, 2017.  URL http://arxiv.org/abs/1709.02457.
  * Real et al. (2017) Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc Le, and Alex Kurakin.  Large-scale evolution of image classifiers.  _arXiv preprint arXiv:1703.01041_ , 2017.
  * Rossi et al. (2014) André Luis Debiaso Rossi, André Carlos Ponce de Leon Ferreira, Carlos Soares, Bruno Feres De Souza, et al.  Metastream: A meta-learning based method for periodic algorithm selection in time-changing data.  _Neurocomputing_ , 127:52–64, 2014.
  * Schlimmer and Granger (1986) Jeffrey C Schlimmer and Richard H Granger.  Beyond incremental processing: Tracking concept drift.  In _AAAI_ , pages 502–507, 1986.
  * Silver and Mercer (2001) Daniel Silver and Robert Mercer.  Selective functional transfer: Inductive bias from related tasks.  In _IASTED International Conference on Artificial Intelligence and Soft Computing (ASC2001)_ , pages 182–189, 2001.
  * Silver and amd Lianghao Li (2013) Daniel L. Silver and Qiang Yang amd Lianghao Li.  Lifelong machine learning systems: Beyond learning algorithms.  In _Lifelong Machine Learning: Papers from the 2013 AAAI Spring Symposium_ , pages 49–55, 2013.
  * Silver and Mercer (1996) Daniel L Silver and Robert E Mercer.  The parallel transfer of task knowledge using dynamic learning rates based on a measure of relatedness.  In _Learning to learn_ , pages 213–233. Springer, 1996.
  * Silver and Mercer (2002) Daniel L Silver and Robert E Mercer.  The task rehearsal method of life-long learning: Overcoming impoverished data.  In _Conference of the Canadian Society for Computational Studies of Intelligence_ , pages 90–101. Springer, 2002.
  * Street and Kim (2001) W. Nick Street and YongSeog Kim.  A streaming ensemble algorithm (sea) for large-scale classification.  In _Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’01, pages 377–382, New York, NY, USA, 2001. ACM.  ISBN 1-58113-391-X.  10.1145/502512.502568.  URL http://doi.acm.org/10.1145/502512.502568.
  * Swersky et al. (2014) Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams.  Freeze-thaw bayesian optimization.  _arXiv preprint arXiv:1406.3896_ , 2014.
  * Thornton et al. (2013) Chris Thornton, Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown.  Auto-weka: Combined selection and hyperparameter optimization of classification algorithms.  In _Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’13, pages 847–855, New York, NY, USA, 2013. ACM.  ISBN 978-1-4503-2174-7.  10.1145/2487575.2487629.  URL http://doi.acm.org/10.1145/2487575.2487629.
  * Thrun and Mitchell (1995) Sebastian Thrun and Tom M Mitchell.  Lifelong robot learning.  _Robotics and autonomous systems_ , 15(1-2):25–46, 1995.
  * van Rijn et al. (2014) Jan N van Rijn, Geoffrey Holmes, Bernhard Pfahringer, and Joaquin Vanschoren.  Algorithm selection on data streams.  In _International Conference on Discovery Science_ , pages 325–336. Springer, 2014.
  * van Rijn et al. (2015) Jan N van Rijn, Geoffrey Holmes, Bernhard Pfahringer, and Joaquin Vanschoren.  Having a blast: Meta-learning and heterogeneous ensembles for data streams.  In _Data Mining (ICDM), 2015 IEEE International Conference on_ , pages 1003–1008. IEEE, 2015.
  * Vanschoren et al. (2014) Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo.  Openml: Networked science in machine learning.  _SIGKDD Explor. Newsl._ , 15(2):49–60, June 2014\.  ISSN 1931-0145.  10.1145/2641190.2641198.  URL http://doi.acm.org/10.1145/2641190.2641198.
  * Wang et al. (2003a) Haixun Wang, Wei Fan, Philip S. Yu, and Jiawei Han.  Mining concept-drifting data streams using ensemble classifiers.  In _Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’03, pages 226–235, New York, NY, USA, 2003a. ACM.  ISBN 1-58113-737-0.  10.1145/956750.956778.  URL http://doi.acm.org/10.1145/956750.956778.
  * Wang et al. (2003b) Haixun Wang, Wei Fan, Philip S Yu, and Jiawei Han.  Mining concept-drifting data streams using ensemble classifiers.  In _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 226–235. AcM, 2003b.
  * Widmer and Kubat (1996) Gerhard Widmer and Miroslav Kubat.  Learning in the presence of concept drift and hidden contexts.  _Machine learning_ , 23(1):69–101, 1996.
  * Žliobaite (2010) Indre Žliobaite.  Change with delayed labeling: When is it detectable?  In _Data Mining Workshops (ICDMW), 2010 IEEE International Conference on_ , pages 843–850. IEEE, 2010.
  * Zoph and Le (2016) Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  _arXiv preprint arXiv:1611.01578_ , 2016.