11institutetext: PUB+ 22institutetext: Ben-Gurion University of the Negev
22email<EMAIL_ADDRESS>
# Monitoring Time Series With Missing Values:
a Deep Probabilistic Approach

Oshri Barazani 11 David Tolpin 22

###### Abstract

Systems are commonly monitored for health and security through collection and
streaming of multivariate time series. Advances in time series forecasting due
to adoption of multilayer recurrent neural network architectures make it
possible to forecast in high-dimensional time series, and identify and
classify novelties early, based on subtle changes in the trends. However,
mainstream approaches to multi-variate time series predictions do not handle
well cases when the ongoing forecasts must include uncertainty, nor they are
robust to missing data. We introduce a new architecture for time series
monitoring based on combination of state-of-the-art methods of forecasting in
high-dimensional time series with full probabilistic handling of uncertainty.
We demonstrate advantage of the architecture for time series forecasting and
novelty detection, in particular with partially missing data, and empirically
evaluate and compare the architecture to state-of-the-art approaches on a
real-world data set.

##  1 Introduction

Modern information systems and operation environments are commonly monitored
through collection and streaming of multivariate time series. The monitoring
tasks comprise both forecasting, for planning of resource allocation and
decision making, and novelty detection and characterization, for ensuring
faultless functioning and early mitigation of failures and threats. Advances
in time series forecasting due to adoption of multilayer recurrent neural
network architectures made it possible to forecast in high-dimensional time
series, and identify and classify novelties (anomalies) early, based on subtle
changes in the trends. However, mainstream approaches to multi-variate time
series modelling do not handle well cases when uncertainty is involved, either
in the input, when some of the observations are missing, or in the output when
the distribution of future observations, rather than their point values, is
predicted. For forecast uncertainty modelling, stochastic latent variable
variants of high-dimensional time series models where introduced, but so far
have had to rely on sampling to account for uncertainty, limiting the
performance of data handling. Imputation schemes were proposed for dealing
with missing data, however, they do not generally give a satisfactory solution
in presence of transient unavailability of some of the data sources (e.g. when
a sensor stops working, or a transport channel malfunctions), which is a
common case with monitoring of complex systems.

A systematic and theoretically founded approach to handling both input and
output uncertainty would thus constitute a significant and welcome
contribution to the theory and practice of monitoring of multivariate time
series. It would also be highly desirable for such approach to facilitate
efficient offline (learning) and online (inference) computations. In this
ongoing research, we propose a deep learning architecture which uses a simple
but powerful extension of traditional recurrent neural network (RNN)
architecture which allows both

  * •

to handle missing inputs in some or all of the components in a multivariate
time series,

  * •

and to accomplish multi-step probabilistic forecasting

in high-dimensional time series, paving a path to better decision making and
finer and more robust anomaly detection and characterization. We evaluate the
architecture on a real-world data set of multivariate time series collected
from a network for cloud computing, and empirically demonstrate advantage of
the proposed architecture over commonly used approaches.

##  2 Problem: Multivariate Time Series Forecasting

The core problem we address is forecasting in a multivariate time series.
Formally, a time series is a matrix $X$ of shape $T\times N$, where $T$ is the
number of time steps and $N$ is the number of dimensions. The time steps are
assumed to be equispaced. A $k$-step probabilistic forecast $\mathcal{F}_{tk}$
at time $t$ is the belief distribution of time series $X_{t+1:t+k}$ for time
steps $t+1...t+k$ given the observed time series $X_{1:t}$ for time steps
$1...t$.

The forecasting is accomplished by applying model $\mathcal{M}_{\theta}$
parameterized by parameters $\theta$ to the observed time series:

$\mathcal{F}_{tk}=\mathcal{M}_{\theta}(X_{1:t})$ (1)

The machine learning task is to devise $\theta^{*}$ that gives the best
forecast, in terms of a certain loss function. A natural loss in the
probabilistic setting is the average negative log likelihood of $\theta$ given
a training data set $\mathcal{X}$ of multiple time series:

$\theta^{*}=\arg\min_{\theta}\mathbb{E}_{X\in\mathcal{X},t\in
1...T-k}\left[-\log\Pr(X_{t+1:t+k}|M_{\theta}(X_{1:t}))\right]$ (2)

When the model is differentiable by $\theta$, the task is usually accomplished
by performing a stochastic gradient loss minimization.

In the basic case, $X$ is real-valued, $X\in\mathbb{R}^{T\times N}$. Here, we
are interested in an extension of the basic case, in which some of the
elements can be missing from $X$, that is $X\in(\mathbb{R}\cup\bot)^{T\times
N}$.

##  3 Architecture: Recurrent Neural Network with Uncertainty Propagation

We introduce here a recurrent neural network architecture which facilitates
uncertainty propagation. The architecture is capable both of handling missing
values and of multi-step forecasting. We begin with description of
conventional forecasting with RNNs. Then, we describe our proposed
architecture as an extension to the conventional model.

RNN$z_{t}$MLP$\mu_{t+1},\sigma_{t+1}$$x_{t}$$h_{t-1}$$h_{t}$RNN$x_{t+1}$$\sim\mathcal{N}(\mu_{t+1},\sigma_{t+1})$
(a) Conventional model

RNN$z_{t}$MLP$\mu_{t+1},\sigma_{t+1}$$\mu_{t}=x_{t},\sigma_{t}=0$$h_{t-1}$$h_{t}$RNN$\mu_{t+1},\sigma_{t+1}$
(b) Model with uncertainty propagation

Figure 1: Time series models

###  3.1 Conventional Forecasting

A popular realization of the forecasting model $\mathcal{M}_{\theta}$ is a
recurrent neural network (RNN), with $\theta$ corresponding to the network
parameters. There is a range of neural recurrent models of varying complexity
to deal with time series forecasting. Most models include a recurrent unit
which threads the state through the time steps, accepts data as inputs and
produces next step predictions as outputs. The simplest model is an RNN with a
fully-connected readout layer to produce forecasts (Figure 1(a)). RNN can be
based on LSTM [13], GRU [8], or another architectural variant, and is often
multi-layer. Architectures may also include intermediate modules, and
sampling-based variational layers [10, 21]. The overall architecture stays
almost the same, with more connections, intermediate modules and sampling-
based variational layers.

#### Input and Output

This architecture normally accepts observation vectors and outputs vectors of
distribution parameters for the belief distribution of the observations at the
next time step. In the simplest case, the network produces a single output for
each input, that is the dimensions of the input and the output vector
coincide. This corresponds to the assumption of homoskedasticity of epistemic
noise, and either the mean squared error (corresponding to the Gaussian error
distribution) or the mean absolute error (corresponding to the Laplace error
distribution) is minimized.

More generally though, the epistemic noise is better modelled
heteroskedastically, and a two-parameter loss distribution, with the location
and the scale as the parameters. In the case of the frequently used normal
(Gaussian) distribution, the output vector consists of means $\mu$ (location)
and standard deviations $\sigma$ (scale) of all dimensions and is twice as
wide as the input.

#### Training

The model is trained to maximize probability of prediction. In the most basic
case, called out-of-sample one-step forecasting, a single step is predicted
for each time step in the series. In an $n$-step time series, steps $1...n-1$
are used as the input, and steps $1...n$ as the ground truth. Following (2),
the network is trained to minimize negative log probability of true
observations given the predicted belief distributions. More generally, a model
can also be trained to predict more than a single step at once into the
future, however this is rarely used in practice because the necessary size of
the training data set grows exponentially with the prediction depth. Instead,
future predictions are produced recurrently during forecasting.

#### Forecasting

Forecasting is accomplished by passing past observations through the model to
obtain forecasts for the future time steps. In the out-of-sample one-step
mode, a single step into the future is forecast. If a longer forecast is
required, the current forecast is entered as the input at the next time step,
time after time, up to the required length. Either the location (the point
forecast) or a random sample from the belief distribution is used as the
future input. Using random samples also allows to assess uncertainty multiple
steps into the future: one can repeatedly sample from the belief distribution
at each future step, and feed the sample as the input to the following step.
Then, based on produced samples at future steps, one can estimate uncertainty
intervals. Such Monte-Carlo handling of uncertainty is quite expensive
computationally though, because the standard deviation of prediction error
decreases as slowly as $\sqrt{N}$ with the number of samples $N$, on one hand,
and uncertainty may, in general, grow exponentially with prediction depth, on
the other hand.

#### Novelty detection

Forecasts produced by the model can be used for a number of purposes,
including decision making and, in particular, novelty (anomaly) detection.
There are two related but different phenomena indicating a novelty in time
series behavior:

  1. 1.

Predicted volatility of the time series is high, that is, future observations
can only be forecast uncertainly (with high variance).

  2. 2.

Probability of actual observations, when observed, given a prediction from a
past state, is low.

Either phenomenon, or both of them, can be used to alert about novelties in
the time series. In recurrent neural network architectures, the hidden state
($h_{t}$ in Figure 1) can be used to identify and classify anomalies.

###  3.2 Forecasting with Uncertainty Propagation

The basic scheme outlined above poses difficulty in applications with high-
dimensional time series and partially missing observations. Sampling based
uncertainty assertion impacts performance, and missing observations are often
imputed heuristically [16, 18]. An architecture which incorporates confidence
about data and in which observed and predicted data are interchangeable is
highly desirable. For example, if out of 5 components 3 were measured and 2
predicted from an earlier step we want to input all of them into the next time
step for further forecasting. In addition, the model architecture should be
capable of robust uncertainty prediction and benefit from training with
multiple steps of out-of-sample data.

Our proposed architecture is based on the observation that if (at least) the
location and the scale are used to represent forecasts, an observation (that
is, certain knowledge at a given step) can also be expressed using two
parameters, by setting the location to the observation, and the scale to 0.
For the normal distribution $\mathcal{N}(\mu,\sigma)$, the location and scale
parameterization is straightforward, corresponding to $\mu$ and $\sigma$,
however other belief distributions can be parameterized by location and scale
as easily, e.g. the log-normal, Gamma, or Laplace distribution. For
conciseness, we will confine further discussion to the case of independent
normal belief distributions for each component; however, other distribution
shapes can also be used. Based on this observation, we propose the following
extension to the conventional RNN-based forecasting model (Figure 1(b)):

  1. 1.

The input, as well as the output, is a vector of distribution parameters. For
the independent normal distributions, the distribution parameter vector
consists of the means followed by the standard deviations. If the data has 5
components, the input will be 10-dimensional. For observed data — measurements
present at the current time step — the standard deviation is zero. For missing
data the input is the mean and the standard deviation as predicted from the
preceding time steps.

  2. 2.

Training can, in principle, be accomplished on data with missing values, but
training on data with missing values incurs performance drawbacks and should
be avoided. First, handling missing values and replacing them with early
predictions introduces contingency in the forward run of the RNN and slows
down significantly the execution during training. Second, missing values
should, in general, themselves be viewed as anomalies. One must be able to
handle them during inference, but should not rely on their presence in the
training data.

Therefore, we devise a scheme for training our model on data that does not
contain missing values. Even in applications where missing values are common
in inference, training data without missing values is usually readily
available. However, since we introduce confidence into the input, we cannot
train the network myopically, in out-of-sample one-step manner — the standard
deviations in the input data will always be zero, and the network will never
learn how to use them. To overcome this, we train on multiple predicted steps.
We feed each prediction, without sampling, as input to the next step and
compute the loss as negative log probability of this number of future points
versus our prediction.

To illustrate, given the data set of 5 dimensions, the input has 10
dimensions. If we train with 3 time steps lookahead, the ground truth will be
a matrix of size $3\times 5$. The prediction against which the likelihood of
this ground truth is computed will be a matrix of size $3\times 10$.
Intuitively, we would expect the predicted standard deviation to increase
along the time axis for each component.

The ability of probabilistic forecasting with uncertainty, in the form of
multivariate normal distributions, far into the future, opens opportunity for
application to more robust novelty detection approaches. Instead of detecting
novelty based on log probability of observations given predictions from the
past [6], which is prone to false positives due to observation noise,
novelties can be detected and analysed by comparing predictions of the same
time point from different points in the past. In this case, KL-divergence
between predictions provides a theoretically sound and robust mechanism for
detection of anomalies, and is in particular relevant for monitoring of large
operation environments with high dimensionality of time series and occasional
missing values and heteroskedastic noise [2, 19].

##  4 Case Study: Monitoring a Computer Cloud

We evaluate the proposed architecture on a data set of monitoring a cluster of
100 computing nodes in the cloud. For each node, the incoming and the outgoing
network traffic (in bytes) and the CPU usage (relative) are logged with 1
minute resolution. 240 hours were logged, resulting in 12000 120-minute
3-dimensional samples. We split the dataset into the training, validation, and
test as 80%, 10%, and 10% correspondingly. Since the original data set does
not have many missing data points, we emulated data sets with missing data by
randomly removing 5%, 10%, 20%, and 50% of the data.

We used a 3-layer GRU-based recurrent neural network with hidden size 64 and
20% dropout between layers. We trained the network with lookahead depths
(number of steps to forecast in the future) 2, 4, 8, and 16 using the Adam
optimizer with learning rate 0.001, training for 20 epochs (sufficient for
convergence). We performed the training on a cloud computing node with 1
NVIDIA T4 GPU, 4 Intel Xeon Platinum CPUs, and 64 Gb memory. The training of a
single model took 20 minutes.

Table 1: Uncertainty propagation vs. ‘replace by the mean‘. missing |  2 |  4 |  8 |  16
---|---|---|---|---
5% |  0.001 |  0.001 |  0.06 |  0.10
10% |  0.001 |  0.002 |  0.08 |  0.11
20% |  0.003 |  0.003 |  0.11 |  0.13
50% |  0.004 |  0.006 |  0.12 |  0.16
Table 2: Uncertainty propagation vs. ‘replace by a random sample‘. missing |  2 |  4 |  8 |  16
---|---|---|---|---
5% |  0.04 |  0.04 |  0.13 |  0.14
10% |  0.06 |  0.06 |  0.16 |  0.24
20% |  0.11 |  0.12 |  0.20 |  0.27
50% |  0.18 |  0.19 |  0.28 |  0.30

We compared our approach with conventional imputation methods ‘replace by the
mean’ and ‘replace by a random sample’. In the ‘replace by the mean’ method, a
missing value is replaced by the mean of the forecast. In the ‘replace by a
random sample’ method, a missing value is replaced by a random sample drawn
from the forecast. As a performance metrics, we used per-point negative log-
likelihood loss on the test set. Tables 1 and 2 show the difference in loss
between uncertainty propagation and ‘replace by the mean’ and ‘replace by a
random sample’, correspondingly. The greater is the number, the worse is the
forecasting by each of the methods compared to uncertainty propagation. One
can see that in all cases uncertainty propagation provides better forecasts
than either of the conventional methods.

Figure 2: Uncertainty propagation vs ‘replace by the mean’. 95% confidence
intervals are shaded.

As an illustration of the advantage of uncertainty propagation, consider
Figure 2, which shows forecasts using uncertainty propagation and ‘replace by
the mean’ in presence of missing values. Forecasts through uncertainty
propagation result in adequate confidence intervals. However, when missing
values are replaced by the mean of the belief distribution, further forecasts
are overconfident and too many observations fall outside of 95% confidence
intervals.

The code and data for the case studies are available at
https://bitbucket.org/dtolpin/dbts-studies/.

##  5 Related Work

There appear to be two interconnected areas related to this research. One area
is uncertainty representation and propagation in recurrent neural models. The
other area is handling of missing values in time series, again in the context
of recurrent neural models in particular.

The importance of uncertainty quantification in deep learning is well
understood [1]. Recurrent neural networks can express forecast uncertainty
through predicting distribution parameters, such as the mean and the standard
deviation, instead of point values [13]. When expressing uncertainty by
closed-form distributions is insufficient, stochastic latent variables are
introduced into RNNs [21, 10, 11]. Uncertainty representation in RNNs is
related to uncertainty propagation and multi-step forecasting. For multi-step
forecasting, uncertainty must be propagated multiple steps into the future.
Uncertainty propagation is usually achieved through random sampling during
training or inference [15, 3, 21]. Our approach differs in that conventional
RNN architectures are leveraged to represent uncertainty in both the input and
the output, and that uncertainty propagation is accomplished
deterministically, without resorting to random sampling, which facilitates
efficient training and inference.

Handling of missing values in time series has inspired research for decades
due to the fact that many otherwise efficient and robust algorithms, in
particular those based on recurrent neural architectures, require that all
values in the time series are present and lie within a valid range [20]. A
widespread approach is to impute the data, that is, to replace missing values
with values inferred from other values in the same time series or in other
time series in the data set [14, 18]. Alternatively, a missing value is
treated as an observation itself, often by introducing an auxiliary indicator
variable [16, 4]. In our work, we take a third approach — a missing value,
either due to an absent observation or in the course of multi-step
forecasting, is replaced by a parametrically specified belief distribution of
the value based on the past observations.

##  6 Discussion and Future Research

We presented a deep probabilistic architecture for uncertainty propagation in
multivariate time series. This architecture organically handles two important
problems in deep time series modelling: missing data and multi-step
forecasting. Empirical evaluation demonstrated that our approach outperforms
conventional baselines in terms of forecasting accuracy, while still being
easy to implement. Since, unlike some other approaches to uncertainty
propagation, our architecture avoids sampling, uncertainty can be propagated
efficiently and represented in closed parametric form, rather than
approximated by samples and posterior intervals.

We confined most of the discussion to the normal uncertainty shape. Other
distributions can be used instead of the normal distributions where
appropriate, provided their parameterization allows to express a certain
observation as well as an uncertain belief. Analysis of distributions for
representing uncertainty and their feasible parameterization is a subject of
ongoing research. Another research direction worth exploring is extension of
the presented architecture to bidirectional recurrent neural networks [5].
Bidirectional RNNs allow to account for both past and future observations
where appropriate, but apparently make uncertainty propagation more
complicated. Still, preliminary results suggest that uncertainty in
bidirectional RNNs can be handled in a similar manner, further facilitating
efficient probabilistic uncertainty propagation in a broader class of deep
learning models for time series.

## Acknowledgements

We thank PUB+ for providing computational facilities for conducting the
empirical evaluation. David Tolpin is partially supported by Israel-U.S.
Industrial Research and Development Foundation’s Cybersecurity technology for
critical power infrastructure AI-based centralized defense and edge resilience
project.

## References

  * [1] Abdar, M., Pourpanah, F., Hussain, S., Rezazadegan, D., Liu, L., Ghavamzadeh, M., Fieguth, P., Cao, X., Khosravi, A., Acharya, U.R., Makarenkov, V., Nahavandi, S.: A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information Fusion 76, 243–297 (2021)
  * [2] Afgani, M., Sinanovic, S., Haas, H.: Anomaly detection using the kullback-leibler divergence metric. In: 2008 First International Symposium on Applied Sciences on Biomedical and Communication Technologies. pp. 1–5 (2008)
  * [3] Alaa, A., Van Der Schaar, M.: Frequentist uncertainty in recurrent neural networks via blockwise influence functions. In: III, H.D., Singh, A. (eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 175–190. PMLR (13–18 Jul 2020)
  * [4] Bansal, P., Deshpande, P., Sarawagi, S.: Missing value imputation on multidimensional time series. Proc. VLDB Endow. 14(11), 2533–2545 (jul 2021)
  * [5] Berglund, M., Raiko, T., Honkala, M., Kärkkäinen, L., Vetek, A., Karhunen, J.T.: Bidirectional recurrent neural networks as generative models. In: Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 28. Curran Associates, Inc. (2015)
  * [6] Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: A survey. ACM Comput. Surv. 41(3) (jul 2009)
  * [7] Che, Z., Purushotham, S., Cho, K., Sontag, D., Liu, Y.: Recurrent neural networks for multivariate time series with missing values. Scientific Reports 8(1) (Apr 2018)
  * [8] Cho, K., van Merriënboer, B., Bahdanau, D., Bengio, Y.: On the properties of neural machine translation: Encoder–decoder approaches. In: Wu, D., Carpuat, M., Carreras, X., Vecchi, E. (eds.) Proceedings of SSST 2014 - 8th Workshop on Syntax, Semantics and Structure in Statistical Translation. pp. 103–111. Proceedings of SSST 2014 - 8th Workshop on Syntax, Semantics and Structure in Statistical Translation, Association for Computational Linguistics (ACL) (2014), funding Information: The authors would like to acknowledge the support of the following agencies for research funding and computing support: NSERC, Calcul Québec, Compute Canada, the Canada Research Chairs and CIFAR. Publisher Copyright: © 2014 Association for Computational Linguistics; 8th Workshop on Syntax, Semantics and Structure in Statistical Translation, SSST 2014 ; Conference date: 25-10-2014
  * [9] Choi, K., Yi, J., Park, C., Yoon, S.: Deep learning for anomaly detection in time-series data: Review, analysis, and guidelines. IEEE Access 9, 120043–120065 (2021). https://doi.org/10.1109/ACCESS.2021.3107975
  * [10] Chung, J., Kastner, K., Dinh, L., Goel, K., Courville, A., Bengio, Y.: A recurrent latent variable model for sequential data. In: Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2. p. 2980–2988. NIPS’15, MIT Press, Cambridge, MA, USA (2015)
  * [11] Fraccaro, M., Sø nderby, S.r.K., Paquet, U., Winther, O.: Sequential neural models with stochastic layers. In: Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 29. Curran Associates, Inc. (2016)
  * [12] Fraccaro, M., Sø nderby, S.r.K., Paquet, U., Winther, O.: Sequential neural models with stochastic layers. In: Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 29. Curran Associates, Inc. (2016)
  * [13] Hochreiter, S., Schmidhuber, J.: Long Short-Term Memory. Neural Computation 9(8), 1735–1780 (11 1997)
  * [14] Kim, Y.J., Chi, M.: Temporal belief memory: Imputing missing data during rnn training. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18. pp. 2326–2332. International Joint Conferences on Artificial Intelligence Organization (7 2018)
  * [15] Li, L., Yan, J., Yang, X., Jin, Y.: Learning interpretable deep state space model for probabilistic time series forecasting. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. p. 2901–2908. IJCAI’19, AAAI Press (2019)
  * [16] Lipton, Z.C., Kale, D., Wetzel, R.: Directly modeling missing data in sequences with rnns: Improved classification of clinical time series. In: Doshi-Velez, F., Fackler, J., Kale, D., Wallace, B., Wiens, J. (eds.) Proceedings of the 1st Machine Learning for Healthcare Conference. Proceedings of Machine Learning Research, vol. 56, pp. 253–270. PMLR, Northeastern University, Boston, MA, USA (18–19 Aug 2016)
  * [17] Su, Y., Zhao, Y., Niu, C., Liu, R., Sun, W., Pei, D.: Robust anomaly detection for multivariate time series through stochastic recurrent neural network. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. p. 2828–2837. KDD ’19, Association for Computing Machinery, New York, NY, USA (2019)
  * [18] Suo, Q., Yao, L., Xun, G., Sun, J., Zhang, A.: Recurrent imputation for multivariate time series with missing values. In: 2019 IEEE International Conference on Healthcare Informatics (ICHI). pp. 1–3 (2019). https://doi.org/10.1109/ICHI.2019.8904638
  * [19] Tolpin, D.: Population anomaly detection through deep gaussianization. In: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing. p. 1330–1336. SAC ’19, Association for Computing Machinery, New York, NY, USA (2019)
  * [20] Wen, Q., Sun, L., Yang, F., Song, X., Gao, J., Wang, X., Xu, H.: Time series data augmentation for deep learning: A survey. In: Zhou, Z.H. (ed.) Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. pp. 4653–4660. International Joint Conferences on Artificial Intelligence Organization (8 2021), survey Track
  * [21] Yin, Z., Barucca, P.: Stochastic recurrent neural network for multistep time series forecasting. In: Mantoro, T., Lee, M., Ayu, M.A., Wong, K.W., Hidayanto, A.N. (eds.) Neural Information Processing. pp. 14–26. Springer International Publishing, Cham (2021)


n/(nt_{n}(x)^{2})\leq(\log n/n)^{1/3}\|p\|_{\infty}^{2/3}.$ Thus for all
sufficiently large $n,$ we have
$\log^{2}n/n\leq\operatorname{P}_{\mathrm{X}}([x\pm t_{n}(x)])\leq n^{-1/4}.$
Applying (59) shows that there exist $a_{n}(x)$ and a constant $A$ independent
of $n,$ such that for any $x\in[0,1],$

$\displaystyle\operatorname{P}_{\mathrm{X}}([x\pm
t_{n}(x)])=\operatorname{P}_{\mathrm{X}}^{n}([x\pm
t_{n}(x)])+a_{n}(x)\sqrt{\frac{\operatorname{P}_{\mathrm{X}}([x\pm
t_{n}(x)])\log n}{n}}$

and $\sup_{x}|a_{n}(x)|\leq A,$ almost surely.

Suppose now that $t_{n}(x)>Q\widehat{t}_{n}(x)$ with
$Q\mathrel{\mathop{\mathchar 58\relax}}=(1+A/\sqrt{\log n}).$ By (3),
$t_{n}(x)<1/\sqrt{\log n}.$ Using the definitions of $t_{n}(x)$ and
$\widehat{t}_{n}(x)$, we have

$\displaystyle\frac{\log n}{n}$
$\displaystyle=t_{n}(x)^{2}\operatorname{P}_{\mathrm{X}}([x\pm t_{n}(x)])$
$\displaystyle=t_{n}(x)^{2}\operatorname{P}_{\mathrm{X}}^{n}([x\pm
t_{n}(x)])+a_{n}(x)t_{n}(x)\sqrt{\frac{t_{n}(x)^{2}\operatorname{P}_{\mathrm{X}}([x\pm
t_{n}(x)])\log n}{n}}$
$\displaystyle>Q^{2}\widehat{t}_{n}(x)^{2}\operatorname{P}_{\mathrm{X}}^{n}([x\pm\widehat{t}_{n}(x)])-A\frac{\sqrt{\log
n}}{n}$ $\displaystyle\geq\Big{(}Q^{2}-\frac{A}{\sqrt{\log
n}}\Big{)}\frac{\log n}{n}$ $\displaystyle>\frac{\log n}{n},$

almost surely. This is a contradiction and hence $t_{n}(x)\leq
Q\widehat{t}_{n}(x),$ almost surely.

Now let $t(x)$ be such that $t_{n}(x)\leq R^{-1}t(x)$ with
$R\mathrel{\mathop{\mathchar 58\relax}}=(1-A/\sqrt{\log n})^{-1/2}>1.$ Arguing
similarly as above, we find that

$\displaystyle\frac{\log n}{n}$
$\displaystyle=t_{n}(x)^{2}\operatorname{P}_{\mathrm{X}}([x\pm t_{n}(x)])$
$\displaystyle=t_{n}(x)^{2}\operatorname{P}_{\mathrm{X}}^{n}([x\pm
t_{n}(x)])+a_{n}(x)t_{n}(x)\sqrt{\frac{t_{n}(x)^{2}\operatorname{P}_{\mathrm{X}}([x\pm
t_{n}(x)])\log n}{n}}$
$\displaystyle\leq\frac{t(x)^{2}}{R^{2}}\operatorname{P}_{\mathrm{X}}^{n}([x\pm
t(x)])+A\frac{\sqrt{\log n}}{n},$

almost surely. Rewriting this gives

$\displaystyle t(x)^{2}\operatorname{P}_{\mathrm{X}}^{n}([x\pm t(x)])\geq
R^{2}\Big{(}1-\frac{A}{\sqrt{\log n}}\Big{)}\frac{\log n}{n}\geq\frac{\log
n}{n},$

almost surely. Since $t(x)$ was arbitrary, applying the definition of the
estimator $\widehat{t}_{n}(x)$ yields $t_{n}(x)\geq R^{-1}\widehat{t}_{n}(x),$
almost surely.

Combined with $t_{n}(x)\leq Q\widehat{t}_{n}(x),$ this proves

$\displaystyle\sup_{x}\,\Big{|}\frac{\widehat{t}_{n}(x)}{t_{n}(x)}-1\Big{|}\leq\Big{|}1-\frac{1}{Q}\Big{|}\vee|R-1|,$

almost surely. For any positive number $u,$
$|1/\sqrt{u}-1|=|1-\sqrt{u}|/\sqrt{u}=|1-u|/(\sqrt{u}(1+\sqrt{u}))\leq|1-u|/\sqrt{u}.$
Without loss of generality, we can assume that $n$ is sufficiently large such
that $\sqrt{\log n}\geq 2A.$ Choosing $u\mathrel{\mathop{\mathchar
58\relax}}=1-A/\sqrt{\log n},$ we then have $u\geq 1/2$ and
$|R-1|=|1/\sqrt{u}-1|\leq\sqrt{2}A/\sqrt{\log n}.$ Since also
$|1-1/Q|=|Q-1|/Q\leq|Q-1|=A/\sqrt{\log n},$ this proves that for any
sufficiently large $n,$

$\displaystyle\sup_{x}\,\Big{|}\frac{\widehat{t}_{n}(x)}{t_{n}(x)}-1\Big{|}\leq\Big{|}1-\frac{1}{Q}\Big{|}\vee|R-1|\leq\frac{\sqrt{2}A}{\sqrt{\log
n}},$

almost surely. The proof is complete. ∎

##  Appendix C Proofs for Section 3

######  Lemma 28.

If $\operatorname{P}_{\mathrm{X}}\in\mathcal{P}_{n}(D)$ for some $n>0$ and
$D\geq 2,$ then for any $x\in[0,1]$ and any $t>0,\
\operatorname{P}_{\mathrm{X}}([x\pm t])>0$.

###### Proof.

Suppose that for some $x_{0}\in[0,1]$ and some $t>0,\
\operatorname{P}_{\mathrm{X}}([x_{0}\pm t])=0$. We prove that this implies the
contradiction $1=\operatorname{P}_{\mathrm{X}}([0,1])=0.$ By considering sub-
intervals, one can without loss of generality assume that $t\leq\sqrt{\log
n}\sup_{x\in[0,1]}t_{n}(x).$ Therefore one can apply (LDP) to obtain that
$\operatorname{P}_{\mathrm{X}}([x_{0}\pm 2t])\leq
D\operatorname{P}_{\mathrm{X}}([x_{0}\pm t])=0.$ We have $[x_{0}-t\pm
t]\subset[x_{0}\pm 2t]$ and $[x_{0}+t\pm t]\subset[x_{0}\pm 2t]$. Therefore
$\operatorname{P}_{\mathrm{X}}([x_{0}-t\pm
t])=\operatorname{P}_{\mathrm{X}}([x_{0}+t\pm t])=0$. One can then repeat the
previous step $\lceil 1/t\rceil$ times to obtain that

$\displaystyle 1=\operatorname{P}_{\mathrm{X}}([0,1])\leq\sum_{i=0}^{\lceil
t^{-1}\rceil}\operatorname{P}_{\mathrm{X}}([x-it\pm
t])+\operatorname{P}_{\mathrm{X}}([x+it\pm t])=0.$

Since this is a contradiction, the proof is complete. ∎

###### Proof of Lemma 9.

Let $u_{n}\mathrel{\mathop{\mathchar 58\relax}}=\sqrt{\log
n}\sup_{x\in[0,1]}t_{n}(x)$. Since $\operatorname{P}_{\mathrm{X}}$ admits a
Lebesgue density, $x,t\mapsto\operatorname{P}_{\mathrm{X}}([x\pm t])$ is
continuous on $[0,1]\times(0,1]$. By virtue of Lemma 28,
$x\mapsto\operatorname{P}_{\mathrm{X}}([x\pm t])$ is strictly positive on
$[0,1]\times(0,1]$. Therefore
$f\colon(x,\eta)\mapsto\operatorname{P}_{\mathrm{X}}([x\pm
2\eta])/\operatorname{P}_{\mathrm{X}}([x\pm\eta])$ is continuous on
$[0,1]\times(0,1].$ In particular $f$ is continuous on the compact set
$[0,1]\times[u_{n},1].$ Therefore $f(x,\eta)$ is upper bounded on
$[0,1]\times[u_{n},1]$ by some constant $D^{\prime}$ depending on
$\operatorname{P}_{\mathrm{X}}$. Also, for all $\eta\leq u_{n},\ f(x,\eta)\leq
D$ by assumption. Combining both, means that for all
$x,\eta\in[0,1]\times(0,1],\ f(x,\eta)\leq
D_{n}(\operatorname{P}_{\mathrm{X}})\mathrel{\mathop{\mathchar
58\relax}}=D^{\prime}\vee\sup_{\eta\leq u_{n}}\sup_{x\in[0,1]}\ f(x,\eta)\leq
D^{\prime}\vee D$ and hence
$\operatorname{P}_{\mathrm{X}}\in\mathcal{P}_{G}(D_{n}(\operatorname{P}_{\mathrm{X}}))$.
∎

The following lemma provides an easily checkable condition for which a
distribution $\operatorname{P}_{\mathrm{X}}\in\mathcal{M}$ with monotone
density $p$ is doubling.

######  Lemma 29 (Lemma 3.2 from [11]).

Let $w$ be a locally integrable, monotonic function on $\mathbb{R}_{+}$ and
define $F\colon x\mapsto\int_{0}^{x}w(u)\,du.$ Denote by $\mu$ the measure
$A\in\mathcal{B}(\mathbb{R}_{+})\mapsto\int_{A}w(u)\,\mathrm{d}u\in\mathbb{R}_{+}.$
If $w$ is increasing, then $\mu$ is doubling if and only if there exists a
constant $\gamma\in(0,1/2)$ such that for all $x,$

$\displaystyle\gamma F(2x)\leq F(x).$

If $w$ is decreasing, then $\mu$ is doubling if and only if there exists a
constant $\gamma\in(1,2)$ such that, for all $x,$

$\displaystyle\gamma F(x)\leq F(2x).$

Where doubling means that there exists a constant $D^{\prime}\geq 2$ such that
for all $x\in\mathbb{R}_{+}$ and all $\eta>0,\ \mu([x\pm 2\eta])\leq
D^{\prime}\mu([x\pm\eta]).$

###### Proof of Lemma 10.

We first prove that
$\operatorname{P}_{\mathrm{X}}\in\mathcal{P}_{G}(4\bar{p}/\underline{p})$. To
see that, for any $x\in[0,1],$ consider $\eta>0$. We have $(4\eta\wedge
1)\overline{p}\geq\operatorname{P}_{\mathrm{X}}([x\pm
2\eta])\geq\operatorname{P}_{\mathrm{X}}([x\pm\eta])\geq(\eta\wedge
1)\underline{p}.$ Therefore

$\displaystyle\frac{\operatorname{P}_{\mathrm{X}}([x\pm
2\eta])}{\operatorname{P}_{\mathrm{X}}([x\pm\eta])}\leq\frac{(4\eta\wedge
1)\bar{p}}{(\eta\wedge 1)\underline{p}}\leq
4\frac{\overline{p}}{\underline{p}}.$

We now prove (9). For all $n>2$ and $x\in[0,1],\,t_{n}(x)<1$ and
$t_{n}(x)\underline{p}\leq\operatorname{P}_{\mathrm{X}}([x\pm t_{n}(x)])\leq
2t_{n}(x)\overline{p}$. By using the definition of the spread function
$t_{n}$, we obtain

$\displaystyle t_{n}(x)^{3}\underline{p}\leq\frac{\log n}{n}\leq
2t_{n}(x)^{3}\overline{p},$

which, once rearranged, yields the desired inequality. ∎

######  Proof of Lemma 11.

To simplify the notation, we write
$\operatorname{P}=\operatorname{P}_{\mathrm{X}}.$ Let $\alpha>0$ and $p\colon
x\mapsto(\alpha+1)x^{\alpha}\mathds{1}(x\in[0,1])$.

The function $w\colon x\mapsto(\alpha+1)x^{\alpha}$ is increasing on
$(0,\infty)$ and for any
$x>0,\,\operatorname{P}([0,x])/\operatorname{P}([0,2x])=1/2^{\alpha+1}\in(0,1/2)$.
Therefore a measure $\mu$ with Lebesgue density $w$ is doubling in the sense
of Lemma 29. Denote the doubling constant by $D.$ The restriction of $\mu$ to
the interval $[0,1]$ yields the distribution $\operatorname{P}.$ We show now
that $\operatorname{P}\in\mathcal{P}_{G}(D^{3}).$ To see this, we distinguish
two cases, either $\eta>1$ or $0<\eta\leq 1$. If $\eta>1$ then
$\operatorname{P}([x\pm
2\eta])=1=\operatorname{P}_{\mathrm{X}}([x\pm\eta])\leq(D\vee
2)\operatorname{P}_{\mathrm{X}}([x\pm\eta])$ which proves (LDP) in this case.
Now, if $\eta\in(0,1]$, for any $x\in[0,1]$, we have
$\operatorname{P}_{\mathrm{X}}([x\pm\eta])=\mu([x\pm\eta]\cap[0,1])\geq
D^{-2}\mu([x\pm\eta]).$ Consequently,

$\displaystyle\frac{\operatorname{P}_{\mathrm{X}}([x\pm
2\eta])}{\operatorname{P}_{\mathrm{X}}([x\pm\eta])}=\frac{\mu([x\pm
2\eta]\cap[0,1])}{\mu([x\pm\eta]\cap[0,1])}\leq D^{2}\frac{\mu([x\pm
2\eta])}{\mu([x\pm\eta])}\leq D^{3}$

and thus $\operatorname{P}\in\mathcal{P}_{G}(D^{3}).$

By assumption $n\geq 9$. According to Lemma 19 and Remark 1, we can split
$[0,1]$ into three intervals $I_{1}\mathrel{\mathop{\mathchar
58\relax}}=[0,a_{n}),\ I_{2}\mathrel{\mathop{\mathchar
58\relax}}=[a_{n},b_{n}]$ and $I_{3}\mathrel{\mathop{\mathchar
58\relax}}=(b_{n},1]$ such that $t_{n}(a_{n})=a_{n},\ t_{n}(b_{n})=1-b_{n}$,
on $I_{1},\ t_{n}(x)>x$, on $I_{2},\ t_{n}(x)\leq x\vee(1-x)$ and on $I_{3},\
t_{n}(x)\geq 1-x.$ Moreover, from the expression for the derivative
$t_{n}^{\prime}$ in Lemma 19 $(iii)$ and from the fact that $p$ is strictly
increasing, we know that $t_{n}$ is strictly decreasing on $[0,b_{n})$ and
$t_{n}$ is strictly increasing on $(b_{n},1]$. We now derive expressions for
the boundaries $a_{n},b_{n}$.
Derivation of $a_{n}$: The solution $a_{n}$ of the equation $t_{n}(x)=x$ must
satisfy $2^{\alpha+1}a_{n}^{\alpha+3}=\frac{\log n}{n},$ which can be
rewritten as

$\displaystyle a_{n}=\left(\frac{\log
n}{2^{\alpha+1}n}\right)^{1/(\alpha+3)}.$

Derivation of $b_{n}$: We solve the equation $t_{n}(b_{n})=1-b_{n}$ for
$b_{n}\in[0,1]$. Using the definition of the spread function, we obtain

$\displaystyle
t_{n}(b_{n})^{2}\big{(}1-(1-2t_{n}(b_{n}))^{\alpha+1}\big{)}=\frac{\log
n}{n}.$ (60)

By Lemma 19 $(ii)$, we know that for $n>9,$ $b_{n}>1/2$ and therefore
$t_{n}(b_{n})<1/2.$ Since $\alpha>0,$ Bernoulli’s inequality guarantees
$1-2(\alpha+1)t_{n}(b_{n})\leq(1-2t_{n}(b_{n}))^{\alpha+1}\leq
1-2t_{n}(b_{n}).$ Rewriting yields

$\displaystyle\left(\frac{\log n}{2(\alpha+1)n}\right)^{1/3}\leq
t_{n}(b_{n})=1-b_{n}\leq\left(\frac{\log n}{2n}\right)^{1/3}.$

We now focus on the behaviour of $t_{n}$ in each of those regimes.
First regime, $t_{n}(x)\geq x$: Simple calculus leads to

$\displaystyle t_{n}(0)$ $\displaystyle=\left(\frac{\log
n}{n}\right)^{1/(\alpha+3)}\ \text{ and}\ \ t_{n}(a_{n})=\left(\frac{\log
n}{2^{\alpha+1}n}\right)^{1/(\alpha+3)}.$ (61)

As mentioned before, the spread function $t_{n}$ is strictly decreasing on
$I_{1}$ and for all $x\in I_{1},\ t_{n}(a_{n})\leq t_{n}(x)\leq t_{n}(0).$
Hence,

$\displaystyle\left(\frac{\log n}{2^{\alpha+1}n}\right)^{1/(\alpha+3)}\leq
t_{n}(x)\leq\left(\frac{\log n}{n}\right)^{1/(\alpha+3)},$ (62)

completing the proof of (10).
Second regime, $t_{n}(x)\leq x\wedge(1-x)$: For $x\in I_{2}$, we have

$\displaystyle\operatorname{P}([x\pm t_{n}(x)])$
$\displaystyle=\int_{x-t_{n}(x)}^{x+t_{n}(x)}(\alpha+1)u^{\alpha}\,du.$

Using that in this regime $t_{n}(x)\leq x$ implies
$\int_{x-t_{n}(x)}^{x+t_{n}(x)}u^{\alpha}\,du\leq\int_{x-t_{n}(x)}^{x+t_{n}(x)}(x+t_{n}(x))^{\alpha}\,du\leq
2t_{n}(x)(2x)^{\alpha}.$ Similarly,
$\int_{x-t_{n}(x)}^{x+t_{n}(x)}u^{\alpha}\,du\geq\int_{x}^{x+t_{n}(x)}x^{\alpha}\,du=t_{n}(x)x^{\alpha}.$
Using the definition of $t_{n}$ and the previous inequalities, we get

$\displaystyle(\alpha+1)x^{\alpha}t_{n}(x)^{3}\leq\frac{\log n}{n}$
$\displaystyle\leq 2^{\alpha+1}(\alpha+1)x^{\alpha}t_{n}(x)^{3},$

which, once rearranged, yields, for all $x\in I_{2}$,

$\displaystyle\left(\frac{\log
n}{2^{\alpha+1}(\alpha+1)nx^{\alpha}}\right)^{1/3}\leq
t_{n}(x)\leq\left(\frac{\log n}{(\alpha+1)nx^{\alpha}}\right)^{1/3}.$ (63)

Third regime, $t_{n}(x)\geq 1-x$: As mentioned before, in this regime the
spread function $t_{n}$ is strictly increasing. We already have suitable
bounds for the value of $t_{n}(b_{n})$ and need now an upper bound for the
value of $t_{n}(1)$. We have
$\operatorname{P}([1-t_{n}(1),1])=1-(1-t_{n}(1))^{\alpha+1}\geq
1-(1-t_{n}(1))=t_{n}(1)$. Therefore, $t_{n}(1)^{3}\leq\log n/n$ and
$t_{n}(1)\leq(\log n/n)^{1/3}.$ Combining the bounds for $t_{n}(b_{n})$ and
$t_{n}(1)$ yields that for any $x\in I_{3},$

$\displaystyle\left(\frac{\log n}{2(\alpha+1)n}\right)^{1/3}\leq
t_{n}(x)\leq\left(\frac{\log n}{n}\right)^{1/3}.$ (64)

Using that $b_{n}>1/2$ and $2^{\alpha}x^{\alpha}\geq 1$ for $x\geq 1/2,$ the
bounds in the second and third regime can be combined into

$\displaystyle\left(\frac{\log
n}{2^{\alpha+1}(\alpha+1)nx^{\alpha}}\right)^{1/3}\leq
t_{n}(x)\leq\left(\frac{\log n}{nx^{\alpha}}\right)^{1/3}\ \ \text{for
}a_{n}\leq x\leq 1.$

This proves (11).

Therefore, Theorem 4 applies. ∎

##  Appendix D Proofs for Section 5

###### Proof of Lemma 12.

By Theorem 4, $\int_{0}^{1}(\widehat{f}_{n}(x)-f_{0}(x))^{2}q(x)\,dx\leq
K\int_{0}^{1}t_{n}^{\operatorname{P}}(y)^{2}q(y)\,dy$ with probability tending
to one as $n\to\infty$. To obtain the first inequality with
$K^{\prime\prime}=4K^{2}$, it is therefore enough to show that

$\displaystyle\int_{0}^{1}t_{n}^{\operatorname{P}}(y)^{2}q(y)\,dy\leq
4\int_{0}^{1}t_{n}^{\operatorname{P}}(x)\operatorname{Q}\big{(}[x\pm
t_{n}^{\operatorname{P}}(x)]\big{)}\,dx.$ (65)

To verify (65), observe that for any $y,\ t_{n}^{\operatorname{P}}(y)\leq 1$
and hence

$\displaystyle\int_{0}^{1}t_{n}^{\operatorname{P}}(y)^{2}q(y)\,dy\leq
2\int_{0}^{1}\int_{[y\pm
t_{n}^{\operatorname{P}}(y)/2]\cap[0,1]}\,dx\,t_{n}^{\operatorname{P}}(y)q(y)\,dy.$
(66)

By construction of the second integral, we have that $|x-y|\leq
t_{n}^{\operatorname{P}}(y)/2.$ From Lemma 19, we know that
$t_{n}^{\operatorname{P}}$ is a $1$-Lipschitz function and therefore,
$|t_{n}^{\operatorname{P}}(x)-t_{n}^{\operatorname{P}}(y)|\leq|x-y|\leq
t_{n}^{\operatorname{P}}(y)/2,$ implying $t_{n}^{\operatorname{P}}(y)/2\leq
t_{n}^{\operatorname{P}}(x)\leq 3t_{n}^{\operatorname{P}}(y)/2$ so that
$x\in[y\pm t_{n}^{\operatorname{P}}(y)/2]$ implies $y\in[x\pm
t_{n}^{\operatorname{P}}(x)]$. This proves the inclusions

$\displaystyle I\mathrel{\mathop{\mathchar
58\relax}}=\Big{\\{}(x,y)\mathrel{\mathop{\mathchar
58\relax}}(x,y)\in\big{[}y\pm
t_{n}^{\operatorname{P}}(y)/2\big{]}\cap[0,1]\times[0,1]\Big{\\}}$
$\displaystyle\subseteq\Big{\\{}(x,y)\mathrel{\mathop{\mathchar
58\relax}}(x,y)\in[y\pm
t_{n}^{\operatorname{P}}(x)]\cap[0,1]\times[0,1]\Big{\\}}$
$\displaystyle\subseteq\Big{\\{}(x,y)\mathrel{\mathop{\mathchar
58\relax}}(x,y)\in[0,1]\times[x\pm
t_{n}^{\operatorname{P}}(x)]\cap[0,1]\Big{\\}}.$

Combined with (66) and $t_{n}^{\operatorname{P}}(y)/2\leq
t_{n}^{\operatorname{P}}(x)$, it follows that

$\displaystyle\int_{0}^{1}t_{n}^{\operatorname{P}}(y)^{2}q(y)\,dy$
$\displaystyle\leq 4\int_{I}t_{n}^{\operatorname{P}}(x)q(y)\,dy\,dx$
$\displaystyle=4\int_{0}^{1}t_{n}^{\operatorname{P}}(x)\int_{[x\pm
t_{n}^{\operatorname{P}}(x)]\cap[0,1]}q(y)\,dy\,dx$
$\displaystyle=4\int_{0}^{1}t_{n}^{\operatorname{P}}(x)\operatorname{Q}\big{(}[x\pm
t_{n}^{\operatorname{P}}(x)]\big{)}\,dx,$

completing the proof for (65) and therefore establishing the first inequality
of the lemma.

To prove the second inequality, observe that

$\frac{1}{t_{n}^{\operatorname{P}}(x)}=\sqrt{\frac{n}{\log
n}\operatorname{P}([x\pm
t_{n}^{\operatorname{P}}(x)])}\leq\sqrt{2\frac{n}{\log
n}t_{n}^{\operatorname{P}}(x)\|p\|_{\infty}},$

which can be rewritten into
$1/t_{n}^{\operatorname{P}}(x)\leq(2\|p\|_{\infty}n/{\log n})^{1/3}.$ ∎

###### Proof of Lemma 13.

In Lemma 11, we already checked the conditions of Theorem 4.

We first prove the result for $\alpha<1$ using Lemma 12. For $\alpha\in(0,1),$
notice that since $t_{n}^{\operatorname{P}}(x)\leq 1,$ we have for any $x\leq
1/2,$ $\operatorname{P}([x\pm
t_{n}^{\operatorname{P}}(x)])\geq\int_{x}^{x+t_{n}^{\operatorname{P}}(x)/2}(\alpha+1)u^{\alpha}\,du\geq
x^{\alpha}t_{n}^{\operatorname{P}}(x)/2.$ Similarly, for any $x\geq 1/2,$
$\operatorname{P}([x\pm
t_{n}^{\operatorname{P}}(x)])\geq\operatorname{P}([1/2\pm
t_{n}^{\operatorname{P}}(x)])\geq(1/2)^{\alpha}t_{n}^{\operatorname{P}}(x)/2.$
Combining both cases gives the lower bound $\operatorname{P}([x\pm
t_{n}^{\operatorname{P}}(x)])\geq
2^{-\alpha}x^{\alpha}t_{n}^{\operatorname{P}}(x)/2.$ Since also
$\operatorname{Q}([x\pm t_{n}^{\operatorname{P}}(x)])\leq
2t_{n}^{\operatorname{P}}(x)$ and $\|p\|_{\infty}=(1+\alpha),$ Lemma 12 yields
for $\alpha<1$ that

$\displaystyle\int_{0}^{1}\big{(}\widehat{f}_{n}(x)-f_{0}(x)\big{)}^{2}q(x)\,dx$
$\displaystyle\leq 2^{1/3}K^{\prime\prime}\Big{(}\frac{\log
n}{n}\Big{)}^{2/3}\|p\|_{\infty}^{1/3}\int_{0}^{1}\frac{\operatorname{Q}([x\pm
t_{n}^{\operatorname{P}}(x)])}{\operatorname{P}([x\pm
t_{n}^{\operatorname{P}}(x)])}\,dx$ $\displaystyle\leq
2^{\alpha+7/3}K^{\prime\prime}\Big{(}\frac{\log
n}{n}\Big{)}^{2/3}(1+\alpha)\int_{0}^{1}x^{-\alpha}\,dx$
$\displaystyle\lesssim\Big{(}\frac{\log n}{n}\Big{)}^{2/3},$

with probability tending to one as $n\to\infty.$

Due to the infinite integral, the previous argument does not extend to the
case $\alpha\geq 1.$ Using a refined argument based on the bounds for the
spread function in Example 2, we now prove the claim for any $\alpha>0.$

Following Example 2, for any $\alpha>0,$ let $a_{n}=(\log
n/n2^{\alpha+1})^{1/(\alpha+3)}\asymp(\log n/n)^{1/(\alpha+3)}$, and observe
that

$\displaystyle\begin{split}\int_{0}^{1}\big{(}\widehat{f}_{n}(x)-f_{0}(x)\big{)}^{2}q(x)\,dx&\lesssim\int_{0}^{1}t_{n}^{\operatorname{P}}(x)^{2}\,dx\\\
&\lesssim a_{n}\left(\frac{\log
n}{n}\right)^{2/(\alpha+3)}+\int_{a_{n}}^{1}\left(\frac{\log
n}{nx^{\alpha}}\right)^{2/3}\,dx\\\ &\lesssim\left(\frac{\log
n}{n}\right)^{3/(\alpha+3)}+\left(\frac{\log
n}{n}\right)^{2/3}\underbrace{\int_{a_{n}}^{1}x^{-2\alpha/3}\,dx}_{A_{n}},\end{split}$

with probability tending to one as $n\to\infty.$ If $\alpha=3/2$ then
$A_{n}=-\log(a_{n})\asymp\log n$; if $\alpha\neq 3/2,$ then
$A_{n}\asymp|1-a_{n}^{1-2\alpha/3}|$. Combining the two cases yields the
claim. ∎

###### Proof of Theorem 14.

Theorem 8 shows that there are numbers $N,M$ and an event $A$ that has
probability one, such that on $A,$ we have $\max_{n\geq N,m\geq
M}\sup_{x\in[0,1]}|\widehat{t}_{n}^{\
\operatorname{P}}(x)/t_{n}^{\operatorname{P}}(x)-1|\vee|\widehat{t}_{m}^{\
\operatorname{Q}}(x)/t_{m}^{\operatorname{Q}}(x)-1|\leq 1/2.$ Let us now
always work on the event $A$. Note that

$\displaystyle\max_{n\geq N,m\geq M}\,\sup_{x\in[0,1]}\
\frac{\widehat{t}_{n}^{\
\operatorname{P}}(x)}{t_{n}^{\operatorname{P}}(x)}\vee\frac{t_{n}^{\operatorname{P}}(x)}{\widehat{t}_{n}^{\
\operatorname{P}}(x)}\vee\frac{\widehat{t}_{m}^{\
\operatorname{Q}}(x)}{t_{m}^{\operatorname{Q}}(x)}\vee\frac{t_{m}^{\operatorname{Q}}(x)}{\widehat{t}_{m}^{\
\operatorname{Q}}(x)}\leq 2.$

In particular, we have that $\tfrac{1}{2}(t_{n}^{\operatorname{P}}(x)\wedge
t_{m}^{\operatorname{Q}}(x))\leq\widehat{t}_{n}^{\
\operatorname{P}}(x)\wedge\widehat{t}_{m}^{\ \operatorname{Q}}(x)\leq
2(t_{n}^{\operatorname{P}}(x)\wedge t_{m}^{\operatorname{Q}}(x)).$ By Theorem
4, there exists a $K^{\prime}$ such that the event $A_{n,m}(f)$, defined
through

$\displaystyle\sup_{x}\frac{|\widehat{f}_{n}^{(1)}(x)-f(x)|}{t_{n}^{\operatorname{P}}(x)}\vee\frac{|\widehat{f}_{m}^{(2)}(x)-f(x)|}{t_{m}^{\operatorname{Q}}(x)}\leq
K^{\prime},$

satisfies
$\sup_{f\in\operatorname{Lip}(1-\delta)}\operatorname{P}_{\\!f}(A_{n,m}(f))\to
1$ as $n\to\infty$ and $m\to\infty.$ Thus on the event $A_{n,m}(f)\cap A,$

$\displaystyle\frac{|\widehat{f}_{n,m}(x)-f(x)|}{t_{n}^{\operatorname{P}}(x)\wedge
t_{m}^{\operatorname{Q}}(x)}$ $\displaystyle\leq
2\frac{|\widehat{f}_{n}^{(1)}(x)-f(x)|\mathbf{1}(\widehat{t}_{n}^{\
\operatorname{P}}(x)\leq\widehat{t}_{m}^{\
\operatorname{Q}}(x))+|\widehat{f}_{m}^{(2)}(x)-f(x)|\mathbf{1}(\widehat{t}_{n}^{\
\operatorname{P}}(x)>\widehat{t}_{m}^{\
\operatorname{Q}}(x))}{\widehat{t}_{n}^{\
\operatorname{P}}(x)\wedge\widehat{t}_{m}^{\ \operatorname{Q}}(x)}$
$\displaystyle\leq
2K^{\prime}\frac{t_{n}^{\operatorname{P}}(x)}{\widehat{t}_{n}^{\
\operatorname{P}}(x)}+2K^{\prime}\frac{t_{m}^{\operatorname{Q}}(x)}{\widehat{t}_{m}^{\
\operatorname{Q}}(x)}$ $\displaystyle\leq 8K^{\prime}.$

Taking $K=8K^{\prime}$ shows then that

$\displaystyle\sup_{f\in\operatorname{Lip}(1-\delta)}\
\operatorname{P}_{\\!f}\left(\sup_{x\in[0,1]}\frac{|\widehat{f}_{n,m}(x)-f(x)|}{t_{n}^{\operatorname{P}}(x)\wedge
t_{m}^{\operatorname{Q}}(x)}>K\right)\leq\sup_{f\in\operatorname{Lip}(1-\delta)}\
\operatorname{P}_{\\!f}(A_{n,m}(f)^{c})+\ \operatorname{P}_{\\!f}(A^{c})\to
0,$

as $n\to\infty$ and $m\to\infty.$ ∎

###### Proof of Theorem 15.

To shorten the notation, we suppress the dependence of
$\operatorname{P}_{\mathrm{X}}^{n}$ and $\operatorname{Q}_{\mathrm{X}}^{n}$ on
$n,$ write $N\mathrel{\mathop{\mathchar 58\relax}}=n+m$ for the size of the
combined samples, and set $t_{n,m}(x)\mathrel{\mathop{\mathchar
58\relax}}=t_{n}^{\operatorname{P}}(x)\wedge t_{m}^{\operatorname{Q}}(x)$. In
a first step of the proof, we construct a number of disjoint intervals on
which the mixture distribution
$\overline{\operatorname{P}}=\tfrac{n}{N}\operatorname{P}_{\mathrm{X}}+\tfrac{m}{N}\operatorname{Q}_{\mathrm{X}}$
assigns sufficiently much mass. Let $\psi_{N}=(\log N/N)^{1/3}$ and
$M_{N}=\lceil 1/(2\psi_{N})\rceil.$ Furthermore, let $N_{0}$ be the smallest
positive integer, such that for all $N\geq N_{0},$

$\displaystyle N^{1/4}\leq\frac{1}{6(2C_{\infty}-1)}\Big{(}\frac{N}{\log
N}\Big{)}^{1/3}\quad\text{and}\ \ \psi_{N}\leq\frac{1}{4}.$ (67)

Clearly, $N_{0}$ only depends on $C_{\infty}.$ We now prove the theorem for
all $N\geq N_{0}.$ The second constraint implies that
$M_{N}\psi_{N}\leq(1/(2\psi_{N})+1)\psi_{N}\leq 3/4.$

For $1\leq k\leq M_{N},$ consider the intervals
$I_{k}\mathrel{\mathop{\mathchar 58\relax}}=[(2k-1)\psi_{N}\pm\psi_{N}].$ By
construction, $\cup_{k=1}^{M_{N}}I_{k}\supseteq[0,1].$ Define moreover
$s_{N}\mathrel{\mathop{\mathchar
58\relax}}=|\\{k\in\\{1,\ldots,M_{N}\\}\mathrel{\mathop{\mathchar
58\relax}}\overline{\operatorname{P}}(I_{k})\geq\psi_{N}\\}|$ and
$\alpha_{N}\mathrel{\mathop{\mathchar 58\relax}}=s_{N}/M_{N}.$ We now derive a
lower bound for the fraction $\alpha_{N}.$ Using $M_{N}\psi_{N}\leq 3/4$ in
the last step, we have

$\displaystyle 1\leq\sum_{k=1}^{M_{N}}\overline{\operatorname{P}}(I_{k})$
$\displaystyle\leq\sum_{k\mathrel{\mathop{\mathchar
58\relax}}\,\overline{\operatorname{P}}(I_{k})\leq\psi_{N}}\psi_{N}+\sum_{k\mathrel{\mathop{\mathchar
58\relax}}\,\overline{\operatorname{P}}(I_{k})>\psi_{N}}\overline{\operatorname{P}}(I_{k})$
$\displaystyle\leq(M_{N}-s_{N})\psi_{N}+2s_{N}C_{\infty}\psi_{N}$
$\displaystyle=(1-\alpha_{N})M_{N}\psi_{N}+2\alpha_{N}M_{N}C_{\infty}\psi_{N}$
$\displaystyle\leq\big{(}1+\alpha_{N}(2C_{\infty}-1)\big{)}\frac{3}{4}.$

Rewriting this, we find

$\displaystyle\alpha_{N}\geq\frac{1}{3(2C_{\infty}-1)}=\mathrel{\mathop{\mathchar
58\relax}}2b.$

Thus, there exist at least $b(N/\log N)^{1/3}$ intervals $I_{k}$ such that
$\overline{\operatorname{P}}(I_{k})\geq\psi_{N}$. By a slight abuse of
notation, denote by $k_{1},\dots,k_{s_{N}}$ the indexes for which
$\overline{\operatorname{P}}(I_{k})\geq\psi_{N}.$ Together with (67),
$s_{N}\geq b(N/\log N)^{1/3}\geq N^{1/4}$ for all $N\geq N_{0}.$ Write
$x_{j}\mathrel{\mathop{\mathchar 58\relax}}=(2k_{j}-1)\psi_{N}$ for the center
of the interval $I_{k_{j}}$ and observe that using the definition of the
spread function,

$\displaystyle t_{n,m}(x_{j})^{2}\overline{\operatorname{P}}(I_{k})$
$\displaystyle\leq
t_{n}^{\operatorname{P}}(x_{j})^{2}\frac{n}{N}\operatorname{P}\big{(}[x_{j}\pm
t_{n}^{\operatorname{P}}(x_{j})]\big{)}+t_{m}^{\operatorname{Q}}(x_{j})^{2}\frac{n}{N}\operatorname{Q}\big{(}[x_{j}\pm
t_{m}^{\operatorname{Q}}(x_{j})]\big{)}$ $\displaystyle\leq\frac{\log n+\log
m}{N}$ $\displaystyle\leq 2\frac{\log N}{N}.$

If $t_{n,m}(x_{j})>\sqrt{2}\psi_{N},$ then,
$t_{n,m}(x_{j})\overline{\operatorname{P}}(I_{k})>2\psi_{N}^{3}=2\log N/N,$
which is a contradiction. Therefore, $t_{n,m}(x_{j})\leq\sqrt{2}\psi_{N}$ for
all $j=1,\ldots,s_{N}.$

We now apply the multiple testing lower bound together with Theorem 2.5 from
[36]. In order to do so we construct $s_{N}+1>0$ hypotheses
$f_{0},\dots,f_{s_{N}}\in\operatorname{Lip}(1)$ such that,

  1. $(i)$

For all $i,j\in\\{0,\dots,s_{N}\\},$ with $i\neq j,$ we have

$\Big{\|}\frac{f_{i}-f_{j}}{t_{n,m}}\Big{\|}_{\infty}\geq\frac{1}{6},$

  2. $(ii)$

$\frac{1}{s_{N}}\sum_{i=1}^{s_{N}}\operatorname{KL}(\operatorname{P}_{f_{i}}||\operatorname{P}_{f_{0}})\leq\frac{\log
s_{N}}{9},$

where $\operatorname{KL}(\cdot||\cdot)$ denotes the Kullback-Leibler
divergence and $\operatorname{P}_{\\!f}$ is the distribution of the data in
the nonparametric regression model with covariate shift (19). Since the loss
$\ell(f,g)=\|(f-g)/t_{n,m}\|_{\infty}$ defines a distance, the result follows
from Theorem 2.5 from [36] once we have established $(i)$ and $(ii).$

Recall that $x_{j}\mathrel{\mathop{\mathchar 58\relax}}=(2k_{j}-1)\psi_{N}$
are the centers of the $s_{N}$ intervals $I_{k_{1}},\ldots,I_{k_{m}}.$ Set
$f_{0}=0$ and for any $i=1,\dots,s_{N}$, consider the function $f_{i}\colon
x\mapsto(t_{n,m}(x_{i})/6-|x-x_{i}|)_{+},$ with
$(z)_{+}\mathrel{\mathop{\mathchar 58\relax}}=\max(z,0).$ By construction,
$f_{i}\in\operatorname{Lip}(1).$ As shown above, $t_{n,m}(x_{i})\leq
2\psi_{N}.$ This implies that the support of $f_{i}$ is contained in the
interval $[x_{i}-t_{n,m}(x_{i})/6,x_{i}+t_{n,m}(x_{i})/6]\subset I_{k_{i}}.$
Thus, for different $i,j,$ the functions $f_{i}$ and $f_{j}$ have disjoint
support. Since $\|f_{i}\|_{\infty}=t_{n,m}(x_{i})/6,$ we obtain for $i\neq j,$

$\displaystyle\Big{\|}\frac{f_{i}-f_{j}}{t_{n,m}}\Big{\|}_{\infty}\geq\frac{f_{i}(x_{i})}{t_{n,m}(x_{i})}=\frac{1}{6},$

and this proves $(i).$

To verify $(ii),$ we first show the known formula

$\displaystyle\operatorname{KL}(\operatorname{P}_{\\!f},\operatorname{P}_{g})=\frac{n}{2}E_{X\sim\operatorname{P}}[(f(X)-g(X))^{2}]+\frac{m}{2}E_{X\sim\operatorname{Q}}[(f(X)-g(X))^{2}].$
(68)

that holds for all $L^{2}[0,1]$-functions $f,g.$ To see this, observe that for
any function $h,$

$\displaystyle\operatorname{P}_{h}=\bigotimes_{i=1}^{n}\operatorname{P}_{h,i}\otimes\bigotimes_{j=1}^{m}\operatorname{Q}_{h,j},$

where $\operatorname{P}_{h,i}$ denotes the distribution of the $i$-th
observation $Y_{i}=h(X_{i})+\varepsilon_{i}$ with $X_{i}\sim\operatorname{P}$
and $Q_{h,j}$ denotes the $(j+n)$-th observation
$Y_{j+n}=h(X_{j+n})+\varepsilon_{j+n}$ with $X_{j+n}\sim\operatorname{Q}.$ If
$R_{1},S_{1}$ are two probability measures defined on the same measurable
space and $R_{2},S_{2}$ are two probability measures defined on the same
measurable space, then $\operatorname{KL}(R_{1}\otimes R_{2},S_{1}\otimes
S_{2})=\operatorname{KL}(R_{1},S_{1})+\operatorname{KL}(R_{2},S_{2}),$ see
e.g. $(iii)$ on p.85 in [36]. Therefore,
$\operatorname{KL}(\operatorname{P}_{\\!f},\operatorname{P}_{g})=\sum_{i=1}^{n}\operatorname{KL}(\operatorname{P}_{f,i},\operatorname{P}_{g,i})+\sum_{j=1}^{m}\operatorname{KL}(\operatorname{Q}_{f,j},\operatorname{Q}_{g,j}).$
If $\operatorname{P}_{h,i|X_{i}}$ denotes the conditional distribution of
$Y_{i}=h(X_{i})+\varepsilon_{i}$ given $X_{i},$ it follows from the definition
of the Kullback-Leibler divergence that
$\operatorname{KL}(\operatorname{P}_{f,i},\operatorname{P}_{g,i})=E_{X\sim\operatorname{P}}[\operatorname{KL}(\operatorname{P}_{f,i|X_{i}},\operatorname{P}_{g,i|X_{i}})].$
By using that $\varepsilon_{i}$ is standard normal, some elementary
computations show moreover that
$\operatorname{KL}(\operatorname{P}_{f,i|X_{i}},\operatorname{P}_{g,i|X_{i}})=(f(X_{i})-g(X_{i}))^{2}/2,$
see also Corollary 2.1 in [36]. By following the same arguments,
$\operatorname{KL}(\operatorname{Q}_{f,j},\operatorname{Q}_{g,j})=E_{X\sim\operatorname{Q}}[(f(X)-g(X))^{2}]/2.$
Putting everything together proves then (68).

Now, we use that $f_{0}=0,$ $\|f_{j}\|_{\infty}\leq t_{n,m}(x_{j})/4,$
$t_{n,m}(x)=t_{n}^{\operatorname{P}}(x)\wedge t_{m}^{\operatorname{Q}}(x),$
and the definition of the spread function, to obtain for $j=1,\dots,M_{N},$

$\displaystyle\operatorname{KL}(\operatorname{P}_{f_{j}}||\operatorname{P}_{f_{0}})$
$\displaystyle=\frac{n}{2}\operatorname{E}_{X\sim\operatorname{P}}\big{[}f_{j}(X)^{2}\big{]}+\frac{m}{2}\operatorname{E}_{X\sim\operatorname{Q}}\big{[}f_{j}(X)^{2}\big{]}$
$\displaystyle\leq\frac{n}{2}\int_{x_{j}-t_{n}^{\operatorname{P}}(x_{j})}^{x_{j}+t_{n}^{\operatorname{P}}(x_{j})}f_{j}(t)^{2}p(t)\,\,dt+\frac{m}{2}\int_{x_{j}-t_{m}^{\operatorname{Q}}(x_{j})}^{x_{j}+t_{m}^{\operatorname{Q}}(x_{j})}f_{j}(t)^{2}p(t)\,\,dt$
$\displaystyle\leq\frac{n}{72}t_{n}^{\operatorname{P}}(x_{j})^{2}\operatorname{P}\left([x_{j}\pm
t_{n}^{\operatorname{P}}(x_{j})]\right)+\frac{m}{72}t_{m}^{\operatorname{Q}}(x_{j})^{2}\operatorname{P}\left([x_{j}\pm
t_{m}^{\operatorname{Q}}(x_{j})]\right)$ $\displaystyle\leq\frac{\log n+\log
m}{72}$ $\displaystyle\leq\frac{\log N}{36}.$

Recall that $s_{N}\geq N^{1/4}.$ Averaging over the $s_{N}$ hypotheses and
using that $\log s_{N}\geq\tfrac{1}{4}\log N,$ we find

$\displaystyle\frac{1}{s_{N}}\sum_{j=1}^{s_{N}}\operatorname{KL}(\operatorname{P}_{f_{j}}||\operatorname{P}_{f_{0}})\leq\frac{\log
N}{36}\leq\frac{\log s_{N}}{9}.$

Therefore, the conditions of Theorem 2.5 in [36] are satisfied with $M=s_{N},$
$s=1/12,$ and
$d(\widehat{\theta},\theta)=\|(\widehat{f}-f)/t_{n,m}\|_{\infty}.$ From the
conclusion of this theorem, the claim follows. ∎

###### Proof of Theorem 7.

The theorem can be viewed as a special case of Theorem 15. In particular the
proof of Theorem 15 carries over to this setting by taking $m=0$ and
$t_{m}^{\operatorname{Q}}(x)=\infty,$ such that
$t_{n,m}(x)=t_{n}^{\operatorname{P}}(x)$ for all $x.$ ∎

###### Proof of Lemma 16.

We write $\operatorname{P}=\operatorname{P}_{\mathrm{X}}$ and
$\operatorname{Q}=\operatorname{Q}_{\mathrm{X}}.$ Suppose that
$t_{m+n}^{\widetilde{\operatorname{P}}}(x)>t_{m}^{\operatorname{Q}}(x)\sqrt{\frac{\log(m+n)}{\log
m}}>t_{m}^{\operatorname{Q}}(x)$, then

$\displaystyle\frac{\log(n+m)}{\log m}\frac{\log m}{m}$
$\displaystyle=\frac{\log(n+m)}{\log
m}t_{m}^{\operatorname{Q}}(x)^{2}\operatorname{Q}([x\pm
t_{n}^{\operatorname{Q}}(x)])$
$\displaystyle<\frac{m+n}{m}\bigg{[}t_{m+n}^{\widetilde{\operatorname{P}}}(x)^{2}\left(\frac{n}{n+m}\operatorname{P}\big{(}[x\pm
t_{m+n}^{\widetilde{\operatorname{P}}}(x)]\big{)}+\frac{m}{m+n}\operatorname{Q}\big{(}[x\pm
t_{n+m}^{\widetilde{\operatorname{P}}}(x)]\big{)}\right)\bigg{]}$
$\displaystyle=\frac{\log(n+m)}{m}$

which is a contradiction. Therefore
$t_{m+n}^{\widetilde{\operatorname{P}}}(x)\leq
t_{m}^{\operatorname{Q}}(x)\sqrt{\frac{\log(m+n)}{\log m}}.$ By symmetry, one
concludes that
$t_{m+n}^{\widetilde{\operatorname{P}}}(x)\leq\sqrt{\tfrac{\log(m+n)}{\log
n}}t_{n}^{\operatorname{P}}(x)$. This proves
$t_{n+m}^{\widetilde{\operatorname{P}}}(x)\leq
t_{m}^{\operatorname{Q}}(x)\sqrt{\tfrac{\log(m+n)}{\log m}}\wedge
t_{n}^{\operatorname{P}}(x)\sqrt{\tfrac{\log(m+n)}{\log n}}$.

To prove the second part of the claim, we prove that there are positive
constants $C^{\prime\prime}$ and $M,$ such that
$t_{m+n}^{\widetilde{P}}(x)\leq
C^{\prime\prime}(t_{n}^{\operatorname{P}}(x)\wedge
t_{m}^{\operatorname{Q}}(x))$ for all $n\geq m\geq M.$ Since
$\log(n),\log(m)>1$ for $n,m>2,$ the result holds then with
$C^{\prime}=C^{\prime\prime}\vee\sqrt{\log(2M)}$ for all $n\geq m>2.$

Observe that if $t_{m}^{\operatorname{Q}}(x)\sqrt{\log(m+n)/\log m}\leq
t_{n}^{\operatorname{P}}(x)\sqrt{\log(m+n)/\log n},$ then,

$\displaystyle\sqrt{\frac{\log m}{m}}\leq
t_{m}^{\operatorname{Q}}(x)\leq\sqrt{\frac{\log m}{\log
n}}t_{n}^{\operatorname{P}}(x)\leq\sqrt{\frac{\log m}{\log n}}Cn^{-\kappa},$

where the first inequality follows from the definition of the spread function
which implies $t_{m}^{\operatorname{Q}}(x)^{2}\geq
t_{m}^{\operatorname{Q}}(x)^{2}\operatorname{Q}([x\pm
t_{m}^{\operatorname{Q}}(x)])=\log m/m.$ The last display can be rewritten
into the form $n^{2\kappa}\log n\leq Cm,$ implying that $\log m=\log\log
n+2\kappa\log n-\log C.$ Therefore, we have that for sufficiently large
$M,C^{\prime\prime}$ and all $n\geq m\geq M,$
$\sqrt{\log(n+m)/\log(m)}\vee\sqrt{\log(n+m)/\log(m)}\leq\sqrt{\log(2n)/\log(m)}\leq
C^{\prime\prime}.$ Together with the first inequality of the lemma, we then
have

$\displaystyle t_{n+m}^{\widetilde{\operatorname{P}}}(x)\leq
t_{m}^{\operatorname{Q}}(x)\sqrt{\tfrac{\log(m+n)}{\log m}}\wedge
t_{n}^{\operatorname{P}}(x)\sqrt{\tfrac{\log(m+n)}{\log n}}\leq
C^{\prime\prime}\big{(}t_{m}^{\operatorname{Q}}(x)\wedge
t_{n}^{\operatorname{P}}(x)\big{)},$

for all $n\geq m\geq M.$ ∎

###### Proof of Lemma 17.

Using Theorem 14, we have that

$\displaystyle\int_{0}^{1}\big{(}\widehat{f}_{n,m}(x)-f_{0}(x)\big{)}^{2}\,dx\lesssim\int_{0}^{1}\big{(}t_{n}^{\operatorname{P}}(x)\wedge
t_{m}^{\operatorname{Q}}(x)\big{)}^{2}\,dx$

with probability tending to one as $n$ and $m$ tend to infinity. Let
$a_{n}=(\log n/n2^{\alpha+1})^{1/(\alpha+3)}.$ Rewriting the condition
$n^{3/(3+\alpha)}\log^{\alpha/(3+\alpha)}n\ll m$ shows that
$(m/n)^{1/\alpha}>a_{n}$ for all sufficiently large $n.$ Using Lemma 10, Lemma
11 and $m\leq n$, we find that

$\displaystyle\int_{0}^{1}\big{(}t_{n}^{\operatorname{P}}(x)\wedge
t_{m}^{\operatorname{Q}}(x)\big{)}^{2}\,dx$
$\displaystyle\lesssim\int_{0}^{a_{n}}\Big{(}\frac{\log
n}{n}\Big{)}^{\frac{2}{\alpha+3}}\wedge\Big{(}\frac{\log
m}{m}\Big{)}^{\frac{2}{3}}\,dx+\int_{a_{n}}^{1}\Big{(}\frac{\log
n}{nx^{\alpha}}\Big{)}^{\frac{2}{3}}\wedge\Big{(}\frac{\log
m}{m}\Big{)}^{\frac{2}{3}}\,dx$
$\displaystyle\leq\Big{(}\frac{m}{n}\Big{)}^{1/\alpha}\Big{(}\frac{\log
m}{m}\Big{)}^{\frac{2}{3}}+\int_{(m/n)^{1/\alpha}}^{1}\Big{(}\frac{\log
n}{nx^{\alpha}}\Big{)}^{\frac{2}{3}}\,dx$
$\displaystyle\leq\Big{(}\frac{m}{n}\Big{)}^{1/\alpha}\Big{(}\frac{\log
m}{m}\Big{)}^{\frac{2}{3}}+\Big{(}\frac{\log
n}{n}\Big{)}^{2/3}\frac{1}{2\alpha/3-1}\Big{(}\frac{m}{n}\Big{)}^{1/\alpha-2/3}$
$\displaystyle\leq\Big{(}1+\frac{1}{2\alpha/3-1}\Big{)}\Big{(}\frac{m}{n}\Big{)}^{1/\alpha}\Big{(}\frac{\log
n}{m}\Big{)}^{\frac{2}{3}}.$

∎

##  Appendix E Proofs for Section 6

###### Proof of Theorem 18.

Set $T_{n}(x_{0})\mathrel{\mathop{\mathchar
58\relax}}=(\tfrac{\alpha+1}{A})^{1/(2\alpha+1)}(np(x_{0}))^{\alpha/(2\alpha+1)}(\widehat{f}_{n}(x_{0})-f(x_{0}))$.
Let $\varepsilon_{n}$ be such that $n^{-1/2}\ll\varepsilon_{n}\ll
n^{-1/(2\alpha+1)}$. If $F$ denotes the c.d.f. of the design distribution and
$F_{n}$ denotes the empirical c.d.f.
$F_{n}(x)=\tfrac{1}{n}\sum_{i=1}^{n}\mathbf{1}(X_{i}\leq t).$ We have that

$\displaystyle P\Big{(}T_{n}(x_{0})\leq x\Big{)}$
$\displaystyle=P\Big{(}T_{n}(x_{0})\leq
x\cap\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|\geq\varepsilon_{n}\Big{)}+P\Big{(}T_{n}(x_{0})\leq
x\cap\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|<\varepsilon_{n}\Big{)}.$

Using the DKW inequality [25] yields

$\displaystyle\begin{split}P\Big{(}T_{n}(x_{0})\leq
x\cap\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|\geq\varepsilon_{n}\Big{)}&\leq
P\Big{(}\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|\geq\varepsilon_{n}\Big{)}\\\
&\leq
2e^{-2n\varepsilon_{n}^{2}}\underset{n\to\infty}{\longrightarrow}0.\end{split}$
(69)

We now check that all the assumptions of Theorem 1 in [39] are verified on
$\\{\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|<\varepsilon_{n}\\}$. Since
$\varepsilon_{n}\ll n^{-1/(2\alpha+1)}$ we have that
$\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|\ll n^{-1/(2\alpha+1)}$. By definition of
the c.d.f., we also have $F^{\prime}(x_{0})=p(x_{0})>0.$ Applying the setting
of [39] to our case gives $\phi=\sigma^{2}=w\equiv 1$ and
$Y_{i}-f_{0}(X_{i})=\epsilon_{i}\sim N(0,1)$ for all $1\leq i\leq n$.
Therefore, for all $0\leq j_{n}<k_{n}\leq n,$
$(k_{n}-j_{n})^{-1/2}\sum_{i=j_{n}}^{k_{n}}(Y_{i}-f_{0}(X_{i}))\sim\mathcal{N}(0,1).$
Finally, let $Z$ be a random variable with Chernoff distribution. By applying
Theorem 1 of [39] we obtain

$\displaystyle P\Big{(}T_{n}(x_{0})\leq
x\big{|}\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|<\varepsilon_{n}\Big{)}\underset{n\to\infty}{\longrightarrow}P(Z\leq
x).$

Hence, applying DKW again yields
$P(\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|<\varepsilon_{n})\geq
1-2\exp(-2n\varepsilon_{n}^{2})\to 1$ as $n\to\infty$ and

$\displaystyle P\Big{(}T_{n}(x_{0})\leq
x\cap\sup_{y\in\mathbb{R}}|F_{n}(y)-F(y)|<\varepsilon_{n}\Big{)}\underset{n\to\infty}{\longrightarrow}P(Z\leq
x).$ (70)

Combining inequalities (69) and (70) gives
$T_{n}(x_{0})\overset{d}{\longrightarrow}Z$. ∎

Recall that
$\rho_{\eta}(\operatorname{P}_{\mathrm{X}},\operatorname{Q}_{\mathrm{X}})\mathrel{\mathop{\mathchar
58\relax}}=\int_{0}^{1}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\,d\operatorname{Q}_{\mathrm{X}}(x)$
and that for any $\gamma\geq 1$ and any $C>0$, the class $\mathcal{S}$ is
defined as the set of all pairs
$(\operatorname{P}_{\mathrm{X}},\operatorname{Q}_{\mathrm{X}}),$ such that
$\sup_{\eta\in(0,1]}\eta^{\gamma}\rho_{\eta}(\operatorname{P}_{\mathrm{X}},\operatorname{Q}_{\mathrm{X}})\leq
C$.

######  Lemma 30.

If $\alpha\geq 1$, $\operatorname{P}_{\mathrm{X}}$ is the distribution with
Lebesgue density $p\colon x\mapsto(\alpha+1)x^{\alpha}\mathds{1}(x\in[0,1])$
and $\operatorname{Q}_{\mathrm{X}}$ is the uniform distribution on $[0,1]$,
then, there exists a constant $0<C<\infty,$ such that for any
$\varepsilon\in(0,\alpha)$,

$(\operatorname{P}_{\mathrm{X}},\operatorname{Q}_{\mathrm{X}})\in\mathcal{S}(\alpha,C)\setminus\mathcal{S}(\alpha-\varepsilon,C).$

###### Proof.

Consider the function
$f\colon\eta\mapsto\int_{0}^{1}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\,dx$.
It can be checked that $f$ is decreasing and continuous. Consequently, to
prove that $\sup_{\eta\in(0,1]}\eta^{\alpha}f(\eta)$ is bounded, it is
sufficient to prove that $\lim_{\eta\to 0}\eta^{\alpha}f(\eta)<\infty.$ For
$0<\eta<1/10,$

$\displaystyle
f(\eta)=\int_{0}^{\eta}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\,dx+\int_{\eta}^{1-\eta}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\,dx+\int_{1-\eta}^{1}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\,dx.$

We now bound the three terms above. We have

$\displaystyle\int_{0}^{\eta}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\
dx$
$\displaystyle=\int_{0}^{\eta}\frac{1}{(x+\eta)^{\alpha+1}}\,dx\leq\frac{1}{\alpha\eta^{\alpha}},$
$\displaystyle\int_{1-\eta}^{1}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\,dx$
$\displaystyle=\int_{1-\eta}^{1}\frac{1}{1-(x-\eta)^{\alpha+1}}\,dx\leq\int_{1-\eta}^{1}\frac{1}{1-x+\eta}\,dx=\log(2).$

For $x\in(\eta,1-\eta),$ we have, by Bernoulli inequality and the fact that
$\alpha+1>1,\
\operatorname{P}_{\mathrm{X}}([x\pm\eta])=x^{\alpha+1}[(1+\eta/x)^{\alpha+1}-(1-\eta/x)^{\alpha+1}]\geq
x^{\alpha}(\alpha+2)\eta.$ Therefore,

$\displaystyle\int_{\eta}^{1-\eta}\operatorname{P}_{\mathrm{X}}([x\pm\eta])^{-1}\,dx\leq\frac{1}{(\alpha+2)\eta}\left[\frac{1}{(\alpha-1)}\frac{1}{\eta^{\alpha-1}}\mathds{1}(\alpha>1)+\log\Big{(}\frac{1}{\eta}\Big{)}\mathds{1}(\alpha=1)+\mathds{1}(\alpha<1)\right],$

and in any case, $\eta^{\alpha}f(\eta)\leq C$ for some $C>0$. This proves that
$\sup_{\eta\in(0,1]}\eta^{\alpha}f(\eta)$ is bounded and
$(\operatorname{P}_{\mathrm{X}},\operatorname{Q}_{\mathrm{X}})\in\mathcal{S}(\alpha,C).$

For $0<\varepsilon<\alpha$ and $0<\eta\leq(1/2)\wedge\Delta,$

$\displaystyle\eta^{\varepsilon}f(\eta)=\int_{0}^{1}\frac{\eta^{\varepsilon}}{\operatorname{P}_{\mathrm{X}}([x\pm\eta])}\,dx\geq\int_{0}^{\eta}\frac{\eta^{\varepsilon}}{\operatorname{P}_{\mathrm{X}}([0,x+\eta])}\,dx=\frac{1}{2^{\alpha}\alpha}\eta^{\varepsilon-\alpha}\underset{\eta\to
0}{\longrightarrow}\infty,$

proving that for any $\varepsilon\in(0,\alpha),$ then
$(\operatorname{P}_{\mathrm{X}},\operatorname{Q}_{\mathrm{X}})\in\mathcal{S}(\alpha,C)\setminus\mathcal{S}(\alpha-\varepsilon,C).$
This concludes the proof. ∎

## References

  * [1] Kenneth S. Alexander  “Rates of growth and sample moduli for weighted empirical processes indexed by sets”  In _Probab. Theory Related Fields_ 75.3, 1987, pp. 379–423  DOI: 10.1007/BF00318708
  * [2] Benedikt Bauer and Michael Kohler  “On deep learning as a remedy for the curse of dimensionality in nonparametric regression”  In _Ann. Statist._ 47.4, 2019, pp. 2261–2285  DOI: 10.1214/18-AOS1747
  * [3] Jonathan Baxter  “A Bayesian/Information Theoretic Model of Learning to Learn via Multiple Task Sampling”  In _Machine Learning_ 28.1, 1997, pp. 7–39  DOI: 10.1023/A:1007327622663
  * [4] Shai Ben-David and Reba Schuller  “Exploiting Task Relatedness for Multiple Task Learning”  In _Learning Theory and Kernel Machines_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 567–580
  * [5] Lucien Birgé and Pascal Massart  “Rates of convergence for minimum contrast estimators”  In _Probab. Theory Related Fields_ 97.1-2, 1993, pp. 113–150  DOI: 10.1007/BF01199316
  * [6] H.. Brunk  “Maximum likelihood estimates of monotone parameters”  In _Ann. Math. Statist._ 26, 1955, pp. 607–616  DOI: 10.1214/aoms/1177728420
  * [7] H.. Brunk  “On the estimation of parameters restricted by inequalities”  In _Ann. Math. Statist._ 29, 1958, pp. 437–454  DOI: 10.1214/aoms/1177706621
  * [8] Stephen M. Buckley and Paul MacManus  “Singular measures and the key of $G$”  In _Publ. Mat._ 44.2, 2000, pp. 483–489  DOI: 10.5565/PUBLMAT\\_44200\\_07
  * [9] T. Cai and Hongji Wei  “Transfer learning for nonparametric classification: minimax rate and adaptive classifier”  In _Ann. Statist._ 49.1, 2021, pp. 100–128  DOI: 10.1214/20-AOS1949
  * [10] Rich Caruana  “Multitask Learning”  In _Machine Learning_ 28.1, 1997, pp. 41–75  DOI: 10.1023/A:1007379606734
  * [11] David Cruz-Uribe  “Piecewise monotonic doubling measures”  In _Rocky Mountain J. Math._ 26.2, 1996, pp. 545–583  DOI: 10.1216/rmjm/1181072073
  * [12] Konstantin Eckle and Johannes Schmidt-Hieber  “A comparison of deep networks with ReLU activation function and linear spline-type methods”  In _Neural Networks_ 110, 2019, pp. 232–242  DOI: https://doi.org/10.1016/j.neunet.2018.11.005
  * [13] Stéphane Gaïffas  “Uniform estimation of a signal based on inhomogeneous data”  In _Statist. Sinica_ 19.2, 2009, pp. 427–447
  * [14] Sara Geer  “Estimating a regression function”  In _Ann. Statist._ 18.2, 1990, pp. 907–924  DOI: 10.1214/aos/1176347632
  * [15] Sara A. Geer  “Applications of empirical process theory” 6, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, Cambridge, 2000, pp. xii+286
  * [16] László Györfi, Michael Kohler, Adam Krzyżak and Harro Walk  “A distribution-free theory of nonparametric regression”, Springer Series in Statistics  Springer-Verlag, New York, 2002, pp. xvi+647  DOI: 10.1007/b97848
  * [17] Qiyang Han, Tengyao Wang, Sabyasachi Chatterjee and Richard J. Samworth  “Isotonic regression in general dimensions”  In _Ann. Statist._ 47.5, 2019, pp. 2440–2471  DOI: 10.1214/18-AOS1753
  * [18] Qiyang Han and Jon A. Wellner  “Convergence rates of least squares regression estimators with heavy-tailed errors”  In _Ann. Statist._ 47.4, 2019, pp. 2286–2319  DOI: 10.1214/18-AOS1748
  * [19] D.. Hanson, Gordon Pledger and F.. Wright  “On consistency in monotonic regression”  In _Ann. Statist._ 1, 1973, pp. 401–421  URL: http://links.jstor.org/sici?sici=0090-5364(197305)1:3%3C401:OCIMR%3E2.0.CO;2-H&origin=MSN
  * [20] J.-P. Kahane  “Trois notes sur les ensembles parfaits linéaires”  In _Enseign. Math. (2)_ 15, 1969, pp. 185–192
  * [21] Michael Kohler and Sophie Langer  “On the rate of convergence of fully connected deep neural network regression estimates”  In _Ann. Statist._ 49.4, 2021, pp. 2231–2249  DOI: 10.1214/20-aos2034
  * [22] Vladimir Koltchinskii  “Local Rademacher complexities and oracle inequalities in risk minimization”  In _Ann. Statist._ 34.6, 2006, pp. 2593–2656  DOI: 10.1214/009053606000001019
  * [23] Samory Kpotufe and Guillaume Martinet  “Marginal singularity and the benefits of labels in covariate-shift”  In _Ann. Statist._ 49.6, 2021, pp. 3299–3323  DOI: 10.1214/21-aos2084
  * [24] Arun K. Kuchibhotla and Rohit K. Patra  “On least squares estimation under heteroscedastic and heavy-tailed errors”  In _Ann. Statist._ 50.1, 2022, pp. 277–302  DOI: 10.1214/21-aos2105
  * [25] P. Massart  “The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality”  In _Ann. Probab._ 18.3, 1990, pp. 1269–1283  URL: http://links.jstor.org/sici?sici=0091-1798(199007)18:3%3C1269:TTCITD%3E2.0.CO;2-Q&origin=MSN
  * [26] Charles Micchelli and Massimiliano Pontil  “Kernels for Multi–task Learning”  In _Advances in Neural Information Processing Systems_ 17 MIT Press, 2004  URL: https://proceedings.neurips.cc/paper/2004/file/c4f796afbc6267501964b46427b3f6ba-Paper.pdf
  * [27] Reese Pathak, Cong Ma and Martin J Wainwright  “A new similarity measure for covariate shift with applications to nonparametric regression”  In _arXiv preprint arXiv:2202.02837_ , 2022
  * [28] Tim Patschkowski and Angelika Rohde  “Adaptation to lowest density regions with application to support recovery”  In _Ann. Statist._ 44.1, 2016, pp. 255–287  DOI: 10.1214/15-AOS1366
  * [29] Kolyan Ray and Johannes Schmidt-Hieber  “A regularity class for the roots of nonnegative functions”  In _Ann. Mat. Pura Appl. (4)_ 196.6, 2017, pp. 2091–2103  DOI: 10.1007/s10231-017-0655-2
  * [30] Adrien Saumard  “Convergence in sup-norm of least-squares estimators in regression with random design and nonparametric heteroscedastic noise” HAL Id: hal-00528539
  * [31] Johannes Schmidt-Hieber  “Nonparametric regression using deep neural networks with ReLU activation function”  In _Ann. Statist._ 48.4, 2020, pp. 1875–1897  DOI: 10.1214/19-AOS1875
  * [32] Hidetoshi Shimodaira  “Improving predictive inference under covariate shift by weighting the log-likelihood function”  In _J. Statist. Plann. Inference_ 90.2, 2000, pp. 227–244  DOI: 10.1016/S0378-3758(00)00115-4
  * [33] Jake A. Soloff, Adityanand Guntuboyina and Jim Pitman  “Distribution-free properties of isotonic regression”  In _Electronic Journal of Statistics_ 13.2 Institute of Mathematical StatisticsBernoulli Society, 2019, pp. 3243–3253  DOI: 10.1214/19-EJS1594
  * [34] Charles J. Stone  “Optimal rates of convergence for nonparametric estimators”  In _Ann. Statist._ 8.6, 1980, pp. 1348–1360  URL: http://links.jstor.org/sici?sici=0090-5364(198011)8:6%3C1348:OROCFN%3E2.0.CO;2-Q&origin=MSN
  * [35] Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul Buenau and Motoaki Kawanabe  “Direct Importance Estimation with Model Selection and Its Application to Covariate Shift Adaptation”  In _Advances in Neural Information Processing Systems_ 20 Curran Associates, Inc., 2007  URL: https://proceedings.neurips.cc/paper/2007/file/be83ab3ecd0db773eb2dc1b0a17836a1-Paper.pdf
  * [36] Alexandre B. Tsybakov  “Introduction to nonparametric estimation” Revised and extended from the 2004 French original, Translated by Vladimir Zaiats, Springer Series in Statistics  Springer, New York, 2009, pp. xii+214  DOI: 10.1007/b13794
  * [37] Aad W. Vaart and Jon A. Wellner  “Weak convergence and empirical processes” With applications to statistics, Springer Series in Statistics  Springer-Verlag, New York, 1996, pp. xvi+508  DOI: 10.1007/978-1-4757-2545-2
  * [38] Martin J. Wainwright  “High-dimensional statistics” A non-asymptotic viewpoint 48, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, Cambridge, 2019, pp. xvii+552  DOI: 10.1017/9781108627771
  * [39] F.. Wright  “The asymptotic behavior of monotone regression estimates”  In _Ann. Statist._ 9.2, 1981, pp. 443–448  URL: http://links.jstor.org/sici?sici=0090-5364(198103)9:2%3C443:TABOMR%3E2.0.CO;2-R&origin=MSN