FERMILAB-CONF-20-622-CMS-SCD

# Accelerated Charged Particle Tracking with Graph Neural Networks on FPGAs

Aneesh Heintz
Cornell Unviersity
Ithaca, NY 14850, USA
&Vesal Razavimaleki*, Javier Duarte
University of California San Diego
La Jolla, CA 92093, USA
&Gage DeZoort, Isobel Ojalvo, Savannah Thais
Princeton University
Princeton, NJ 08544, USA
&Markus Atkinson, Mark Neubauer
University of Illinois at Urbana-Champaign
Champaign, IL 61820, USA
&Lindsey Gray, Sergo Jindariani, Nhan Tran
Fermi National Accelerator Laboratory
Batavia, IL 60310, USA
&Philip Harris, Dylan Rankin
Massachusetts Institute of Technology
Cambridge, MA, 02139, USA
&Thea Aarrestad, Vladimir Loncar, Maurizio Pierini, Sioni Summers
European Organization for Nuclear Research (CERN)
CH-1211 Geneva 23, Switzerland &Jennifer Ngadiuba
California Institute of Technology
Pasadena, CA 92115, USA &Mia Liu
Purdue University
West Lafayette, IN 47907, USA &Edward Kreinar
HawkEye360
Herndon, VA 20170, USA &Zhenbin Wu
University of Illinois at Chicago
Chicago, IL 60607, USA These two authors contributed equally.Also at Institute
of Physics Belgrade, Belgrad, Serbia.

###### Abstract

We develop and study FPGA implementations of algorithms for charged particle
tracking based on graph neural networks. The two complementary FPGA designs
are based on OpenCL, a framework for writing programs that execute across
heterogeneous platforms, and hls4ml, a high-level-synthesis-based compiler for
neural network to firmware conversion. We evaluate and compare the resource
usage, latency, and tracking performance of our implementations based on a
benchmark dataset. We find a considerable speedup over CPU-based execution is
possible, potentially enabling such algorithms to be used effectively in
future computing workflows and the FPGA-based Level-1 trigger at the CERN
Large Hadron Collider.

##  1 Introduction

In high energy physics (HEP), charged particle tracking [1, 2] is a crucial
task necessary for the accurate determination of the kinematics of the
particles produced in a collision event. The objective of tracking algorithms
is to identify the trajectories of charged particles created in the collisions
that bend in a magnetic field and ionize the material of detectors, providing
position measurements along the trajectory of each particle. Current tracking
algorithms [3, 4, 5, 6, 7, 8] scale worse than quadratically in the number of
hits, which are expected to increase dramatically at higher beam intensities.
This motivates the study of alternative algorithms with different
computational scaling. Another important consideration is the ability to
accelerate these algorithms using highly-parallel heterogeneous computing
resources like graphics processing units (GPUs) and field-programmable gate
arrays (FPGAs) as further improvements in single-core CPU performance may be
limited [9, 10]. Recent efforts [11, 12] have demonstrated the effectiveness
of graph neural networks (GNNs) to correctly classify “segments” belonging to
tracks. Graph-based approaches are well suited to this task because tracking
data can be naturally encoded as a graph structure [13] and GNNs consider
local information between pairs of hits to learn relationships between them in
order to “connect the dots” to infer tracks.

In this paper, we accelerate a GNN [12] for segment classification, based on
the interaction network (IN) architecture [14, 15], with FPGA implementations.
Such implementations enable efficient processing, in both speed and energy
consumption for large HEP datasets. They may also enable the use of GNNs in
the high-throughput, FPGA-based data filter system, known as the Level-1
trigger [16, 17, 18, 19], which has strict sub-microsecond latency
requirements that only FPGAs or application-specific integrated circuits
(ASICs) can meet. We design two complementary implementations using OpenCL
[20] and hls4ml [21, 22], a specialized compiler for converting machine
learning (ML) algorithms into FPGA firmware. We evaluate the resource usage,
latency, and tracking performance of our implementations based on the
benchmark TrackML dataset [1].

##  2 TrackML Data and Interaction Network Models

To benchmark the algorithms, we use the TrackML dataset [1], which consists of
simulated 3D measurements of particles coming from independent collision
events at the LHC. For our application, the data is embedded as a graph by
considering the hits as nodes and pairs of hits on adjacent layers as edges.
The edges corresponding to true track segments are labeled as one and all
others are labeled as zero. The goal of the segment classifier algorithm is to
correctly classify the edges as true or spurious.

We focus the scope of the task by considering the innermost layers of the
detector, which usually correspond to the “pixel” detector of a modern HEP
detector. We consider two subdetector regions in the endcaps, consisting of 7
layers each, and one in the barrel of the TrackML detector, consisting of 4
layers. Edges are constructed from hit pairs on adjacent layers satisfying
$\Delta z<15$ cm and $\Delta\phi/\Delta r<2.62\times 10^{-4}$. Particles with
transverse momentum ($p_{\mathrm{T}}$) greater than a given threshold are used
to define the hits (nodes) and true edges. For the hls4ml model, we consider
graphs corresponding to particle $p_{\mathrm{T}}>2$ GeV, while for the OpenCL
implementation we study the scaling as a function of $p_{\mathrm{T}}$ from 1
to 5 GeV. A characteristic graph for a single event is shown in Fig. 1 for
$p_{\mathrm{T}}>2$ GeV. The graph size depends strongly on the minimum
$p_{\mathrm{T}}$. For $p_{\mathrm{T}}>1$ GeV ($2$ GeV), the event graph
contains approximately 5,300 (1,100) nodes and 16,600 (1,500) edges on
average.

Figure 1:  A characteristic graph of particles with $p_{\mathrm{T}}>2$ GeV for
one event in $x$–$y$ view (upper left) and $r$–$z$ view (upper right). The
black edges correspond to true track segments, while the blue edges are
spurious. GNN architectures used for the hls4ml (middle) and OpenCL (lower)
implementations.

Following the approach of Ref. [11, 12], we define a “segment classifier”
using an IN model [14, 15] to learn which edges connect hits belonging to the
same track. Relative to Ref. [12], the model architecture is simplified for
the more limited task and the FPGA implementations. To implement it with
hls4ml, the model shown in Figure 1 (lower left) is used. The same type of
model is used for the OpenCL implementation, as shown in Figure 1 (lower
right), without encoder and decoder networks and a different IN structure. In
addition, while both models consider the 3 input node features $(r,\phi,z)$,
the hls4ml model considers 4 input edge features $(\Delta r,\Delta\phi,\Delta
z,\Delta R)$, while the OpenCL model does not consider any. Instead, in this
model, the input edge features are zero vectors
$\boldsymbol{e}_{k}=\boldsymbol{0}$, which can be thought of as the “initial
guess” of the edge weights, i.e. all edges are initially assumed to be fake.
Though we show results separately for these specific versions of the models,
the hls4ml and OpenCL implementations we developed are modular and flexible
enough to accommodate both models as well as other permutations. Appendix A
demonstrates this by implementing a smaller version of the second model in
hls4ml. Benchmarking the same model implemented in both frameworks is planned
for future work.

For the hls4ml model, an encoder composed of two neural networks,
$\phi_{1}^{e}$ and $\phi_{1}^{v}$, transforms input node and edge features
into hidden representations. Both $\phi_{1}^{e}$ and $\phi_{1}^{v}$ have two
layers with 8 neurons each and rectified linear unit (ReLU) [23, 24]
activation functions. The IN is divided into two parts: an _edge block_ (or
_relational model_) and a _node block_ (or _object model_). The edge block
network $\phi_{2}^{e}$ takes as input a pair of node features with the
corresponding edge features and has layers of sizes $(8,8)$ with ReLU
activation. The outputs of the $\phi_{2}^{e}$ are updated edge features, which
can be considered “messages” sent between the nodes and aggregated at each
node. The node block network $\phi_{2}^{v}$ takes as input the aggregated
messages and the updated node features and consists of layers of sizes $(8,8)$
with ReLU activation. Finally, the decoder network $\phi_{3}^{v}$ transforms
edge features into an edge weight classifier (the probability for a given edge
to be a true track segment), and has layers of sizes $(8,8,8,1)$ with ReLU
activation on all but the final layer that has a sigmoid activation.

For the model used in the OpenCL implementation, the IN begins with an edge
block where $\phi_{2}^{e}$ has layers of sizes $(250,250,250,1)$ with ReLU
activations except for the final layer, which has a sigmoid activation. This
is followed by a node block where $\phi_{2}^{v}$ has layers of sizes
$(200,200,3)$ with ReLU activations except for the final layer. Subsequently,
the same edge block is repeated to calculate the edge weights. The number of
floating point operations (FLOPs) for both of these models scales with the
number of nodes, number of edges, and size of the neural networks.

##  3 Implementations

OpenCL is an open-source C-based interface for parallel computing on various
hardware platforms, including CPUs, GPUs, digital signal processors (DSPs),
and FPGAs, using task and data-based parallelism [20]. The OpenCL
implementation of the IN adopts a CPU-plus-FPGA coprocessing approach where
the host program on the CPU manages the application, and all computational
operations are accelerated using dedicated kernels deployed on the FPGA that
take capitalize on the device’s hardware architecture to parallelize
operations. The matrix multiplication kernel is repeatedly executed during a
forward pass of the network and leverages the FPGA architecture for an
efficient data-parallel implementation. This kernel uses both 2D local memory
tiling and 2D register blocking to reduce the redundancy and latency of
reading from globally shared off-chip memory. Because the input graph sizes to
the network changes per event, the matrix multiplication kernels pad each
matrix before computing the result. Throughout the forward pass, several
optimizations are made to speed up computation. One example is the use of
double buffering, which allows kernels to transfer data and execute
instructions concurrently. All loops iterations executed in the OpenCL kernels
are “unrolled” to run in parallel, which decreases the latency at the cost of
increased hardware resource consumption. The OpenCL implementation is tested
with an Intel Programmable Accelerator Card featuring an Arria 10 GX 1150
FPGA.

hls4ml [21] is an open-source converter of ML models into FPGA firmware
utilizing Xilinx Vitis [25] high-level synthesis (HLS) [26] for both pure FPGA
hardware applications and coprocessing kernels. In addition to implementing a
GNN using available hls4ml tools, efforts are in progress to extend the
compiler to support basic GNN building blocks. Each forward pass of IN is
pipelined such that matrix multiplications are performed in parallel.
Pipelining is performed at the level of the IN edge and node blocks and the
amount of pipelining is tunable through the _reuse factor_ parameter which
controls the initiation interval (II) of each block. In conjunction with
block-level pipelining, all loops are fully unrolled to decrease latency. All
GNN model inputs are implemented with a streaming interface, which creates a
FIFO that recycles its storage of array elements over each passage of a neural
network block. Streaming decreases resource utilization but may increase
latency. The input graph size is truncated to 112 nodes and 148 edges, which
corresponds to the 95th percentile graph size for the $\eta$ and $\phi$
sectors, and uses zero-padding to make the inputs a uniform size. To make
scans of resources and timing more tractable, we further subdivide these
graphs into quarters of up to 28 nodes and 37 edges just for the purposes of
presentation. Tests of the hls4ml implementation target a Xilinx Kintex
UltraScale (KU) 115 FPGA.

##  4 Results

Figure 2: Resource system area analysis for the OpenCL implementation on an
Arria 10 GX 1150 FPGA over multiple input data precision sizes (left).
Scalability study in terms of latency versus minimum $p_{\mathrm{T}}$ (center)
and event size (right).

For the OpenCL implementation, Fig. 2 (left) compares the resource usage for
input data represented with 8-, 16-, and 32-bit floating point precision. For
most components, operating with lower precision typically leads to lower
resource usage, though the system area is dependent on other factors as well.
Execution times also increase with increasing precision from 8 to 32 bits, but
not substantially, especially for lower minimum $p_{\mathrm{T}}$.
Additionally, lower precision leads to smaller input data sizes, enabling the
implementation to process events at lower $p_{\mathrm{T}}$.

Figure 2 shows how the OpenCL implementation scales with minimum
$p_{\mathrm{T}}$ (center) and input data size (right). Our implementation is
able to process graphs with a minimum $p_{\mathrm{T}}$ as low as 1 GeV, which
is limited by hardware storage, such as host CPU RAM and on-device local RAM.
An increase in input data size increases the execution times. The largest
bottlenecks are matrix multiplication operations and the overhead time that
accompanies the enqueueing the kernels. Even though this overhead time
increases as graph input size increases, enqueueing becomes more efficient.
This scalability study shows that the coprocessing approach in OpenCL is
flexible with respect to data size and can handle significant increases in
data sizes. However, we note that our CPU-FPGA coprocessing implementation is
slower by about a factor of 10 from a pure CPU-based approach. In particular,
CPU-based inference of the same model for $p_{\mathrm{T}}>1$ (5) GeV graphs in
PyTorch [27] is about 86 (2) ms.

For the hls4ml implementation, we first scan the fixed point precision total
bit width to determine its impact on the physics performance of the algorithm
as well as the latency and resource usage on the FPGA. We evaluate the
receiver operating characteristic (ROC) curve for the segment classifier, and
use the area under the curve (AUC) as a performance metric. Figure 3 (far
left) shows the AUC as a function of the total bit precision, while the
integer part is fixed to 6 bits. We see that with 12 total bits, we
effectively reproduce the 32-bit floating point model. Figure 3 (center left)
also shows the latency in clock cycles (for a 5 ns clock period) as a function
of the total bit precision, which ranges from about 650 ns to 1 $\mu$s. For
CPU-based inference of the same model, the latency is about 27 ms for the same
sectorized $p_{\mathrm{T}}>2$ GeV graph in the graph_nets framework [28] based
on TensorFlow [29]. We also scan the reuse factor at constant fixed point
precision of $\langle 16,6\rangle$, to study the resources and timing as a
function of decreasing concurrency. Figure 3 shows the latency (center left)
and resource usage estimates (far right) versus reuse factor. By construction,
the II for the algorithm is equal to the reuse factor. We note that the HLS
lookup table (LUT) usage tends to be overestimated, while the HLS DSP usage
tends to be accurate [21, 30, 31]. Nonetheless, to make the algorithm fit on a
single FPGA, larger reuse factors or bigger FPGAs may be necessary.

Figure 3: Segment classifier AUC versus fixed point precision total bit width
(far left) for the hls4ml implementation. Latency in clock cycles for a 5 ns
clock period (center left) as a function of the total bit width for the hls4ml
implementation. The reuse factor (and thus II) is set to be 8. Latency (center
right) and resource usage estimates (far right) relative to the available
resources on a Xilinx KU 115 FPGA versus reuse factor for fixed total bit
precision of $\langle 16,6\rangle$.

##  5 Summary and Outlook

We develop and study two complementary FPGA implementations of algorithms for
charged particle tracking based on graph neural networks. The first, using
OpenCL, targets CPU-FPGA coprocessing applications and achieves a latency of
between $10$ ms–$1$ s depending on the minimum $p_{\mathrm{T}}$ for full event
graphs, including data transfer and I/O, for the model under consideration.
The second, using hls4ml, targets both coprocessing and custom trigger (ultra
low latency) applications and has an expected latency of 650 ns–1 $\mu$s,
considering only the execution time on the FPGA, for smaller, sectorized input
graphs and a more compact model, although more work is needed to reduce the
resource consumption. Compared to CPU-based execution of the same models, the
speedup for the hls4ml implementation is considerable, but further
optimizations are needed to improve on the CPU latency for the OpenCL
implementation. Continued development in this direction may allow such
algorithms to be used effectively in future computing workflows [32] and the
Level-1 trigger at the LHC. In future work, we plan to study detailed
comparisons of the two implementations based on the same model, as well as
comparing to GPU coprocessors [33]. Other optimizations of the GNN model may
also be possible, such as more efficient architectures [30] and use of
quantization-aware training [31, 34] to reduce the necessary precision.

## Broader Impact

This work may be used to accelerate particle tracking and other reconstruction
algorithms in high energy physics experiments. While accelerated machine
learning on FPGAs has many potential benefits to science and society,
including high-quality, fast data reconstruction and selection in experiments,
automated detector control, or smarter IoT devices, it may also be used for
nefarious purposes, such as surveillance or military unmanned aerial vehicles.

## Acknowledgments and Disclosure of Funding

We acknowledge the Fast Machine Learning collective as an open community of
multi-domain experts and collaborators. This community was important for the
development of this project. The simulations presented for the OpenCL
implementation in this article were performed on computational resources
managed and supported by Princeton Research Computing, a consortium of groups
including the Princeton Institute for Computational Science and Engineering
(PICSciE) and the Office of Information Technology’s High Performance
Computing Center and Visualization Laboratory at Princeton University. Work
for the hls4ml implementation was partially performed on the Pacific Research
Platform Nautilus HyperCluster supported by NSF awards CNS-1730158,
ACI-1540112, ACI-1541349, OAC-1826967, the University of California Office of
the President, and the University of California San Diego’s California
Institute for Telecommunications and Information Technology/Qualcomm
Institute. Thanks to CENIC for the 100 Gpbs networks.

A. H., V. R., and S. T. are supported by IRIS-HEP through the U.S. National
Science Foundation (NSF) under Cooperative Agreement OAC-1836650. J. D. is
supported by the U.S. Department of Energy (DOE), Office of Science, Office of
High Energy Physics Early Career Research program under Award No. DE-
SC0021187. T. A., V. L., M. P., and S. S. are supported by the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation program (Grant Agreement No. 772369). L. G., S. J., and N. T. are
supported by Fermi Research Alliance, LLC under Contract No. DE-AC02-07CH11359
with the U.S. Department of Energy (DOE), Office of Science, Office of High
Energy Physics. P. H. is supported by a Massachusetts Institute of Technology
University grant. Z. W. is supported by the National Science Foundation under
Grants No. 1606321 and 115164.

##  Appendix A Alternative GNN Model in hls4ml

In addition to the first model shown in Fig. 1, we also implement the second
model in hls4ml. In this model, the same architecture is used as the one
implemented in OpenCL, except the neural network sizes are reduced: the
$\phi_{2}^{e}$ network has layers of sizes $(8,8,8,1)$ and $\phi_{2}^{v}$ has
layers of sizes $(8,8,3)$. Figure 4 shows the AUC (far left) and the latency
in clock cycles for a 5 ns clock period (center left) as a function of the
total bit precision, while the integer part is fixed to 6 bits. We see that
above 16 total bits, the quantized model effectively reproduces the 32-bit
floating point model. Figure 4 also shows the latency (center left) and
resource usage estimates (far right) versus reuse factor at a constant fixed
point precision of $\langle 16,6\rangle$. This small implemented model
reasonably fits on a single FPGA with a latency less than 1 $\mu$s.

Figure 4: Alternative GNN segment classifier model implemented in hls4ml. AUC
(far left) and latency (center left) in clock cycles for a 5 ns clock period
as a function of the total bit width. The reuse factor (and thus II) is set to
be 8. Latency (center right) and resource usage estimates (far right) relative
to the available resources on a Xilinx KU 115 FPGA versus reuse factor for
fixed total bit precision of $\langle 16,6\rangle$.

## References

  * [1] S. Amrouche et al., “The tracking machine learning challenge: Accuracy phase”, in  The NeurIPS ’18 Competition, S. Escalera and R. Herbrich, eds., p. 231.  Springer, Cham, Switzerland, 2020.  arXiv:1904.06778.  doi:10.1007/978-3-030-29135-8_9.
  * [2] A. Strandlie and R. Frühwirth, “Track and vertex reconstruction: From classical to adaptive methods”,  Rev. Mod. Phys. 82 (2010) 1419, doi:10.1103/RevModPhys.82.1419.
  * [3] CMS Collaboration, “Description and performance of track and primary-vertex reconstruction with the CMS tracker”,  J. Instrum. (2014) P10009, doi:10.1088/1748-0221/9/10/P10009, arXiv:1405.6569.
  * [4] ATLAS Collaboration, “Performance of the ATLAS track reconstruction algorithms in dense environments in LHC Run 2”,  Eur. Phys. J. C 77 (2017) 673, doi:10.1140/epjc/s10052-017-5225-7, arXiv:1704.07983.
  * [5] P. Billoir, “Progressive track recognition with a Kalman-like fitting procedure”,  Comput. Phys. Comm. 57 (1989) 390, doi:10.1016/0010-4655(89)90249-X.
  * [6] P. Billoir and S. Qian, “Simultaneous pattern recognition and track fitting by the Kalman filtering method”,  Nucl. Instrum. Methods Phys. Res. A 294 (1990) 219, doi:10.1016/0168-9002(90)91835-Y.
  * [7] R. Mankel, “A concurrent track evolution algorithm for pattern recognition in the hera-b main tracking system”,  Nucl. Instrum. Methods Phys. Res. A 395 (1997) 169, doi:10.1016/S0168-9002(97)00705-5.
  * [8] R. Frühwirth, “Application of Kalman filtering to track and vertex fitting”,  Nucl. Instrum. Methods Phys. Res. A 262 (1987) 444, doi:10.1016/0168-9002(87)90887-4.
  * [9] H. Esmaeilzadeh et al., “Dark silicon and the end of multicore scaling”, in  Proceedings of the 38th Annual International Symposium on Computer Architecture, p. 365.  ACM, New York, NY, USA, 2011.  doi:10.1145/2000064.2000108.
  * [10] R. H. Dennard et al., “Design of ion-implanted MOSFET’s with very small physical dimensions”,  IEEE J. Solid-State Circuits 9 (1974) 256, doi:10.1109/JSSC.1974.1050511.
  * [11] S. Farrell et al., “Novel deep learning methods for track reconstruction”, in  4th International Workshop Connecting The Dots 2018.  2018\.  arXiv:1810.06111.
  * [12] X. Ju et al., “Graph neural networks for particle reconstruction in high energy physics detectors”, in  Machine Learning and the Physical Sciences Workshop at the 33rd Annual Conference on Neural Information Processing Systems.  2019\.  arXiv:2003.11603.
  * [13] J. Shlomi, P. Battaglia, and J.-R. Vlimant, “Graph neural networks in particle physics”, doi:10.1088/2632-2153/abbf9a, arXiv:2007.13681. Accepted by _Mach. Learn.: Sci. Tech._
  * [14] P. W. Battaglia et al., “Interaction networks for learning about objects, relations and physics”, in  Advances in Neural Information Processing Systems, volume 29, p. 4502.  2016\.  arXiv:1612.00222.
  * [15] P. W. Battaglia et al., “Relational inductive biases, deep learning, and graph networks”, arXiv:1806.01261.
  * [16] ATLAS Collaboration, “Operation of the ATLAS trigger system in Run 2”,  J. Instrum. 15 (2020) P10004, doi:10.1088/1748-0221/15/10/P10004, arXiv:2007.12539.
  * [17] ATLAS Collaboration, “Technical Design Report for the Phase-II Upgrade of the ATLAS TDAQ System”, ATLAS Technical Design Report CERN-LHCC-2017-020. ATLAS-TDR-029, 2017.
  * [18] CMS Collaboration, “Performance of the CMS Level-1 trigger in proton-proton collisions at $\sqrt{s}=$ 13 TeV”,  J. Instrum. 15 (2020) P10017, doi:10.1088/1748-0221/15/10/P10017, arXiv:2006.10165.
  * [19] CMS Collaboration, “The Phase-2 upgrade of the CMS Level-1 trigger”, CMS Technical Design Report CERN-LHCC-2020-004. CMS-TDR-021, 2020.
  * [20] J. E. Stone, D. Gohara, and G. Shi, “OpenCL: A parallel programming standard for heterogeneous computing systems”,  Comput. Sci. Eng. 12 (2010) 66, doi:10.1109/MCSE.2010.69.
  * [21] J. Duarte et al., “Fast inference of deep neural networks in FPGAs for particle physics”,  J. Instrum. 13 (2018) P07027, doi:10.1088/1748-0221/13/07/P07027, arXiv:1804.06913.
  * [22] V. Loncar et al., “fastmachinelearning/hls4ml: aster”, 10, 2020.  doi:10.5281/zenodo.4161550, https://github.com/fastmachinelearning/hls4ml.
  * [23] V. Nair and G. E. Hinton, “Rectified linear units improve restricted Boltzmann machines”, in  Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML’10, p. 807.  Omnipress, Madison, WI, USA, 2010.
  * [24] X. Glorot, A. Bordes, and Y. Bengio, “Deep sparse rectifier neural networks”, in  Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, G. Gordon, D. Dunson, and M. Dudík, eds., volume 15 of  Proceedings of Machine Learning Research, p. 315.  JMLR, Fort Lauderdale, FL, USA, 4, 2011.
  * [25] Xilinx, Inc., “Vivado design suite user guide: High level synthesis”, 2020\.  https://www.xilinx.com/support/documentation/sw_manuals/xilinx2019_2/ug902-vivado-high-level-synthesis.pdf.
  * [26] D. O’Loughlin et al., “Xilinx vivado high level synthesis: Case studies”, in  Irish Signals & Systems Conference 2014 and 2014 China-Ireland International Conference on Information and Communications Technologies (ISSC 2014/CIICT 2014). 25th IET Year, p. 352.  2014\.  doi:10.1049/cp.2014.0713.
  * [27] A. Paszke et al., “PyTorch: An imperative style, high-performance deep learning library”, in  Advances in Neural Information Processing Systems, H. Wallach et al., eds., volume 32, p. 8024.  Curran Associates, Inc., 2019.  arXiv:1912.01703.
  * [28] DeepMind, “graph_nets”, 2019\.  https://github.com/deepmind/graph_nets.
  * [29] M. Abadi et al., “TensorFlow: Large-scale machine learning on heterogeneous systems”, 2015\.  https://www.tensorflow.org.
  * [30] Y. Iiyama et al., “Distance-weighted graph neural networks on FPGAs for real-time particle reconstruction in high energy physics”, doi:10.3389/fdata.2020.598927, arXiv:2008.03601. Accepted by _Front. Big Data_.
  * [31] G. Di Guglielmo et al., “Compressing deep neural networks on FPGAs to binary and ternary precision with hls4ml”, doi:10.1088/2632-2153/aba042, arXiv:2003.06308. Accepted by _Mach. Learn.: Sci. Technol._
  * [32] D. S. Rankin et al., “FPGAs-as-a-service toolkit (FaaST)”, in  2020 IEEE/ACM International Workshop on Heterogeneous High-performance Reconfigurable Computing (H2RC).  2020\.  arXiv:2010.08556.
  * [33] J. Krupa et al., “GPU coprocessors as a service for deep learning inference in high energy physics”, (2020). arXiv:2007.10359. Submitted to _Mach. Learn.: Sci. Technol._
  * [34] C. N. Coelho et al., “Automatic deep heterogeneous quantization of deep neural networks for ultra low-area, low-latency inference on the edge at particle colliders”, arXiv:2006.10159. Submitted to _Nat. Mach. Intell._


# On uniformly consistent tests

Mikhail Ermakov

(April 2023)

###### Abstract

Necessary and sufficient conditions of uniform consistency are explored. A
hypothesis is simple. Nonparametric sets of alternatives are bounded convex
sets in $\mathbb{L}_{p}$, $p>1$ with "small" balls deleted. The "small" balls
have the center at the point of hypothesis and radii of balls tend to zero as
sample size increases. For problem of hypothesis testing on a density, we show
that, for the sets of alternatives, there are uniformly consistent tests for
some sequence of radii of the balls, if and only if, convex set is relatively
compact. The results are established for problem of hypothesis testing on a
density, for signal detection in Gaussian white noise, for linear ill-posed
problems with random Gaussian noise and so on.

Institute of Problems of Mechanical Engineering RAS, Bolshoy pr., 61, VO,
1991178 St. Petersburg and St. Petersburg State University, Universitetsky
pr., 28, Petrodvoretz, 198504 St. Petersburg, RUSSIA

AMS subject classification: 62F03, 62G10, 62G2

keywords : consistency, uniform consistency, goodness of fit tests, signal
detection.

##  1 Introduction

Compactness assumption is necessary condition for existence of uniformly
consistent estimator [9]. This assumption is also naturally arises if we
explore ill-posed problems with deterministic noise [4]. In some sense
compactness is rather severe assumption allowing to find uniformly consistent
estimator. Now we see that the same severe assumption is necessary in natural
setups of nonparametric hypothesis testing.

We say that family of sets of alternatives are uniformly consistent if, for
these sets of alternatives, there is uniformly consistent family of tests.

Uniform consistency of nonparametric sets of alternatives has been explored
from different viewpoints and different setups. A rather complete bibliography
one can find in [5].

We explore the problem, if hypothesis is simple and nonparametric sets of
alternatives are approaching with hypothesis. The research are based on Le Cam
-Schwartz [17] results. Le Cam and Schwartz [17] have found necessary and
sufficient conditions for existence of uniformly consistent tests and
estimators. These conditions are rather cumbersome and are provided in terms
of $n$-fold products of probability measures. A simple form of this conditions
arises if probability measures of statistical experiment are compact in the
topology of set-wise weak convergence, other words, if densities of
probability measures are uniformly integrable.

By Lemma 2.3 in Gaensler [8], if set is compact in weak topology of set-wise
convergence and there is another weak topology on this set such that the set
is Hausdorff space for this topology then these two topologies coincide on the
set. This allows to point out necessary and sufficient conditions of uniform
consistency in terms of simple natural weak topologies for widespread
statistical models: hypothesis testing on a density, signal detection in
Gaussian white noise, hypothesis testing on intensity of Poisson process,
hypothesis testing on Gaussian covariance operator and so on (see [5]). We can
consider this research as natural complement to previous interesting numerous
results on consistency of nonparametric tests [1, 3, 7, 10, 9, 13, 14, 15,
18].

In [5], sets of alternatives did not depend on sample size (power of signal
and so on). For a long time the necessary and sufficient conditions of uniform
consistency for approaching sets of alternatives remained unclear. Special
examples of indistinquishability of hypotheses have been proposed. The first
result on indistinguishability of hypotheses and alternatives has been
established Le Cam [16]. For hypothesis testing on a density Le Cam [16] has
shown that the center of the ball and the interior of the ball in $L_{1}$ are
indistinguishable. For the problem of signal detection in Gaussian white noise
Ibragimov and Hasminski [9] have proved that the center of a ball and the
interior of a ball in $L_{2}$ are indistinguishable. For the same problem
Burnashev [2] established the indistinguishability of the interior of a ball
in $L_{p}$\- spaces, $p>1$. For other setups we mention Ingster [11] and
Ingster, Kutoyants [12] works. Ingster [11] and Ingster and Kutoyants [12]
showed that we could not distinguish the center of a ball and the interior of
a ball in $L_{2}$ in the problems of hypothesis testing on a density and on an
intensity function of Poisson process respectively.

In [7], we showed that, if sets of alternatives are bounded center-symmetric
convex set with deleted "small" balls in $\mathbb{L}_{2}$ having center at the
zero point of hypothesis, then there are uniformly consistent tests for some
sequence of radii of balls tending to zero as sample size increases, if and
only if, the center-symmetric convex set is relatively compact.

Paper goal is to prove similar results without assumption of center-symmetry
of convex set and to extend this result for deleted balls in $\mathbb{L}_{p}$,
$p>1$. The technique allows to explorer balls from another Banach spaces.
However we does not touch these setups.

##  2 Uniformly consistent sets

###  2.1  Hypothesis testing on a density

Let $X_{1},\ldots,X_{n}$ be i.i.d.r.v.’s having probability measure
$\mathbf{P}$ defined on Borel sets of $\sigma$-field $\mathfrak{B}$ assigned
on a set $S$. Denote $\mathcal{P}$ the set of all probability measures on
$(S,\mathfrak{B})$.

For probability measure $\mathbf{P}_{0}\in\mathcal{P}$ denote
$\mathbb{L}_{p}$, $1<p<\infty$, the set of all real measurable functions $g$
such that

$\|g\|_{p}^{p}=\int_{S}|g|^{p}d\,\mathbf{P}_{0}<\infty.$

For each $\rho>0$ and for each $u\in\mathbb{L}_{p}$, define the ball
$B_{\rho}(u)=\\{\,g\,:\,\|g-u\|_{p}\leq\rho,\,g\in\mathbb{L}_{p}\\}$.

Fix bounded convex set $U\subset\mathbb{L}_{p}$. For any $u\in U$ and any
$\rho>0$, assume that there is bounded function $g\in B_{\rho}(u)\cap U$.

We say that $u\in U$ is internal point of convex set $U$ if for any bounded
function $v\in U$ there is $\lambda<0$ such that $u+\lambda(v-u)\in U$. Note
that traditional topological definition of internal point of set is different
(p.410 [dun]).

Suppose that $f_{0}\equiv 0$ is internal point of $U$.

We explore problem of testing hypothesis

$\mathbb{H}_{0}\,\,:\,\,f\doteq\frac{d\mathbb{P}}{d\mathbb{P}_{0}}-1=f_{0}\doteq
0$

versus alternatives

$\mathbb{H}_{n}\,\,:\,\,f\in V(\rho_{n})=U\setminus B_{\rho_{n}}(f_{0})$

with $\rho_{n}>0$, $\rho_{n}\to 0$ as $n\to\infty$.

For any test $K_{n}$ denote $\alpha(K_{n})=\mathbf{E}_{0}[K_{n}]$ its type I
error probability and denote $\beta(K_{n},f)$ its type II error probability
for alternative $f\in V(\rho_{n})$.

We say that sequence of tests $K_{n}$, $0<\alpha(K_{n},f_{0})\leq\alpha<1$, is
uniformly consistent, if there is $n_{0}>0$ and $\delta>0$ such that, for all
$n>n_{0}$, we have

$\beta(K_{n},V(\rho_{n}))\doteq\sup_{f\in
V(\rho_{n})}\beta(K_{n},f)<1-\alpha-\delta$

Otherwise, we say that sequence of tests $K_{n}$,
$0<\alpha(K_{n},f_{0})\leq\alpha<1$, is uniformly inconsistent.

###### Theorem 2.1

There is a sequence $\rho_{n}\to 0$ as $n\to\infty$ such that sets of
alternatives $V(\rho_{n})$ is uniformly consistent, if and only if, set $U$
are relatively compact in $\mathbb{L}_{p}$.

We say that $r_{n}$ is rates of distinguishability if sets of alternatives
$V(\rho_{1n})$ is uniformly inconsistent for any sequence $\rho_{1n}>0$,
$\rho_{1n}/r_{n}\to 0$ as $n\to\infty$, and sets of alternatives
$V(\rho_{2n})$ is uniformly consistent for any sequence $\rho_{2n}>0$,
$\rho_{2n}/r_{n}\to\infty$ as $n\to\infty$.

In proof of Theorem 2.1, for point zero, we construct set $W$ such that
$U\subset W$ and show that Kolmogorov $n$-width $d_{i}$, $1\leq i<\infty$ of
set $W$ tends to zero. The same reasoning we can conduct for any internal
point $u\in U$ and construct set $W_{u}$, $U\subset W_{u}$ with Kolmogorov
$n$-width $d_{ui}$, $1\leq i<\infty$. If we take $h=u$ in proof of Theorem 2.1
and, by the same reasoning, implementing similarity inequality (3.4), we get
$cd_{i}\leq d_{ui}\leq Cd_{i}$, $1\leq i<\infty$, where coefficients $c,C$ are
proportional to similarity coefficient.

For $\varepsilon>0$ and $\theta\in K$, denote
$M(\varepsilon/c(\theta,\varepsilon)\cap K)$, the largest cardinality of an
$\varepsilon/c$ packing set for $B(\theta,\varepsilon)\cap K$ (see definition
5.4 in [19]). We refer to

$\mathfrak{E}^{loc}(\theta,\varepsilon)=\log
M(\varepsilon/c(\theta,\varepsilon)\cap K)$

as local entropy of set $K$ at the point $\theta$. The same similarity
consideration allow to show that there are $c_{1}$ and $c_{2}$ such that, for
any interior points $\theta_{1}\in K$ and $\theta_{2}\in K$ we have

$\mathfrak{E}^{loc}(\theta,c_{1}\varepsilon)\leq\mathfrak{E}^{loc}(\theta,\varepsilon)\leq\mathfrak{E}^{loc}(\theta,c_{2}\varepsilon).$

This is the base for the proof that we have the same rates of
distinguishability in the problems of hypothesis testing
$\mathbb{H}_{0}\,:\,f=0$ versus $\mathbb{H}_{n}\,:\,f\in U\setminus
B_{\rho_{n}}(0)$ and $\mathbb{H}_{0u}\,:\,f=u$ versus
$\mathbb{H}_{nu}\,:\,f\in U\setminus B_{\rho_{n}}(u)$. If point $u$ depends on
$n$, one can get different rates of distinguishability [20].

+

###### Corollary 2.1

Let a priori information be provided that $f\in U$ where $U$ is bounded convex
set in $\mathbb{L}_{p}$, $p>1$. Then there is uniformly consistent estimator
of $\|f\|_{p}$, if and only if, the set $U$ is relatively compact.

Proof of Theorem 2.1 is based on Theorem 2.2 on uniform consistency of set of
alternatives that does not depend on $n$.

For $p>1$, we explore the problem of testing hypothesis

$\mathbb{H}_{0}\,\,:\,\,f\in W_{0}\subset\mathbb{L}_{p}$

versus alternatives

$\mathbb{H}_{1}\,\,:\,\,f\in W_{1}\subset\mathbb{L}_{p}$

We say that sequence of tests $K_{n}$ is uniformly consistent if

$\lim\sup_{n\to\infty}\,(\sup_{f_{0}\in W_{0}}\alpha(K_{n},f_{0})+\sup_{f\in
W_{1}}\beta(K_{n},f))<1$

###### Theorem 2.2

i. Let $W_{0}$ be bounded set in $L_{p}$, $p>1$. Then there are uniformly
consistent tests if the closures of $W_{0}$ and $W_{1}$ are disjoint in weak
topology.

ii. The converse holds if $W_{1}$ is also bounded sets in $L_{p}$, $p>1$.

Theorem 2.2 follows from Le Cam, Schwartz (p.141, [17]) and Lemma 2.3 in
Ganssler [8] (see Theorem 4.1 in [5] as well).

If closures in weak topology of sets $W_{0}$ and $W_{1}$ are disjoint then
there is a finite number of functions $g_{1},\ldots,g_{k}\in\mathbb{L}_{q}$,
$\frac{1}{p}+\frac{1}{q}=1$, and constants $c_{1},\ldots,c_{k}$ such that, for
any $u\in W_{0}$ there holds $c_{i}\,>\,\int_{S}\,u\,g_{i}\,d\,\mathbf{P}_{0}$
for all $i$, $1\leq i\leq k$, and, for any $v\in W_{1}$, there is index $i$,
$1\leq i\leq k$, such that $\int_{S}\,v\,g_{i}\,d\,\mathbf{P}_{0}\,>\,c_{i}$.

###  2.2 Hypothesis testing on intensity function of Poisson random process

Let we be given $n$ independent realizations $\kappa_{1},\ldots,\kappa_{n}$ of
Poisson random process with mean measure $\mathbf{P}$ defined on Borel sets of
$\sigma$-field $\mathfrak{B}$ assigned on set $S$. Suppose mean measure
$\mathbf{P}$ has intensity function $h(t)=\frac{d\mathbf{P}}{d\nu}(t)$, $t\in
S$. Here $\nu$ is a measure defined on Borel sets of $\sigma$-field
$\mathfrak{B}$ as well and $\nu(S)<\infty$, $\mathbf{P}(S)<\infty$.

Problem is to test a hypothesis $H_{0}\,:\,f(t)\doteq f_{0}=h(t)-1\equiv 0$
versus alternatives $H_{n}\,:\,f\in V(\rho_{n})\subset\mathbb{L}_{p}$, $p>1$.
The definition of sets $V(\rho_{n})$, $\rho_{n}>0$, is the same as in previous
subsection with the unique difference that the densities are replaced with
intensity functions. The definition of internal point of convex set $U$ is
also the same as in the previous subsection.

###### Theorem 2.3

Let $U$ be bounded convex set in $\mathbb{L}_{p}$, $p>1$. Let $f_{0}$ be
internal point of $U$. Then there is sequence $\rho_{n}\to 0$ as $n\to\infty$
such that sets of alternatives $V(\rho_{n})$ are uniformly consistent, if and
only if, set $U$ is relatively compact.

Proof of Theorem 2.3 completely coincides with the proof of Theorem 2.1. It
suffices only to implement Theorem 5.9 in [5] instead of Theorem 2.2.

###  2.3 Signal detection in Gaussian white noise

Suppose we observe a realization of stochastic process
$Y_{\epsilon}(t),t\in(0,1)$, defined by the stochastic differential equation

$dY_{\varepsilon}(t)=S(t)dt+\varepsilon dw(t),\quad\varepsilon>0,$

where $S\in\mathbb{L}_{2}(0,1)$ is unknown signal and $dw(t)$ is Gaussian
white noise.

Let $U$ be bounded convex set in $\mathbb{L}_{2}(0,1)$. We say that $S_{0}\in
U$ is internal point of convex set $U$ if, for any $S\in U$, there is
$\lambda<0$ such that $S_{0}+\lambda(S-S_{0})\in U$.

Denote $B_{r}(S)$ ball in $\mathbb{L}_{p}$, $p>1$, having radius $r>0$ and
center $S\in\mathbb{L}_{2}$.

We wish to test a hypothesis

$\mathbb{H}_{0}\,\,:\,\,S(t)=S_{0}(t)\equiv 0,\quad t\in[0,1],$

versus alternatives

$\mathbb{H}_{\varepsilon}\,\,:\,\,S\in V(\rho_{\varepsilon})=U\setminus
B(\rho_{\varepsilon})\quad\rho_{\varepsilon}>0.$

For any test $K_{\varepsilon}$, $\varepsilon>0$, denote
$\alpha(K_{\varepsilon})=\mathbf{E}_{0}[K_{\varepsilon}]$ its type I error
probability and denote $\beta(K_{\varepsilon},S)$ its type II error
probability for alternative $S\in V(\rho_{\varepsilon})$.

We say that family of tests $K_{\varepsilon}$,
$0<\alpha(K_{\varepsilon})\leq\alpha<1$, $\varepsilon>0$, is uniformly
consistent if there is $\varepsilon_{0}>0$ and $\delta>0$ such that, for all
$0<\varepsilon<\varepsilon_{0}$, we have

$\beta(K_{\varepsilon},V(\rho_{\varepsilon}))=\sup_{S\in
V(\rho_{\varepsilon})}\beta(K_{\varepsilon},S)<1-\alpha-\delta.$

###### Theorem 2.4

Let $U$ be bounded convex set in $\mathbb{L}_{p}$, $p>1$. Let $S_{0}$ be
internal point of $U$. Then there is $\rho_{\varepsilon}\to 0$ as
$\varepsilon\to 0$ such that sets of alternatives $V(\rho_{\varepsilon})$ are
uniformly consistent, if and only if, the set $U$ is relatively compact.

Proof of Theorem 2.3 completely coincides with proof of Theorem 2.1. It
suffices to implement Theorem 5.3 in [5] instead of Theorem 2.2.

###  2.4 Hypothesis testing on a solution of linear ill-posed problem

In Hilbert space $\mathbb{H}$ we observe a realization of Gaussian random
vector

$Y_{\varepsilon}=AS+\varepsilon\xi,\quad\varepsilon>0.$ (2.1)

Hereafter $A:\mathbb{H}\to\mathbb{H}$ is known linear operator and $\xi$ is
Gaussian random vector having known covariance operator
$R:\mathbb{H}\to\mathbb{H}$ and $\mathbf{E}\xi=0$.

Denote $B_{r}(S)$ ball in $\mathbb{H}$, having radius $r>0$ and center
$S\in\mathbb{H}$.

Let $U$ be bounded convex set in $\mathbb{H}$.

We wish to test a hypothesis

$\mathbb{H}_{0}\,\,:\,\,S=S_{0}=0,$

versus alternatives

$\mathbb{H}_{\varepsilon}\,\,:\,\,S\in V_{(}\rho_{\varepsilon})=U\setminus
B_{\rho_{\varepsilon}}(S_{0})\quad\rho_{\varepsilon}>0.$

Below we use the same definition of uniform consistency and similar definition
of interior point as in subsection 2.3.

For any operator $K:\mathbb{H}\to\mathbb{H}$ denote $\mathfrak{R}(K)$ the
rangespace of $K$.

Suppose that the nullspaces of $A$ and $R$ equal zero and
$\mathfrak{R}(A)\subseteq\mathfrak{R}(R^{1/2})$.

###### Theorem 2.5

Let the operator $R^{-1/2}A$ be bounded in $\mathbb{H}$. Let $S_{0}$ be
internal point of $U$. Then there is $\rho_{\varepsilon}\to 0$ as
$\varepsilon\to 0$ such that sets of alternatives $V(\rho_{\varepsilon})$ are
uniformly consistent, if and only if, the set $U$ is relatively compact.

###### Proof 2.1

The statement of Theorem 2.4 hold for the sets of alternatives
$R^{-1/2}A\,V(\rho_{n})$. Thus it suffices to implement the inverse map
$A^{-1}R^{1/2}$ to (2.1) (see [5]).

###  2.5 Hypothesis testing on an operator known with a random error

Let $\Theta$ be the set of all bounded linear operators
$\mathbb{H}\to\mathbb{H}$ where $\mathbb{H}$ is separable Hilbert space.

Let $A\in\Theta$ be an unknown linear operator.

Let for all $S\in H$ we can observe random Gaussian vector

$Y_{7\varepsilon,S}=A\,S+\epsilon\xi_{S}$

with $\mathbf{E}\xi_{S}=0$ and
$\mathbf{E}<\xi_{S_{1}},\xi_{S_{2}}>=<S_{1},S_{2}>$ where $<S_{1},S_{2}>$ is
inner product of vectors $S_{1},S_{2}\in\mathbb{H}$.

Let $U$ be convex set in $\Theta$.

We say that $A_{1}\in U$ is internal point of $U$ if, for any $A\in U$, there
is $\lambda<0$ such that $A_{1}+\lambda(A-A_{1})\in U$.

Denote $A_{0}\in\Theta$ linear operator such that, for any $S\in\mathbb{H}$,
we have $A_{0}S=0$.

For Hilbert-Schmidt norm in $\Theta$, denote $B(r)$ ball in $\Theta$ having
radius $r>0$ and center $A_{0}$.

Let $A_{0}$ be interior point of $U$.

The problem is to test hypothesis $H_{0}\,:\,A=A_{0}$ versus alternatives
$H_{1}\,:\,A\in V(\rho_{\varepsilon})\doteq U\setminus B(\rho_{\varepsilon})$
with $\rho_{\varepsilon}>0$.

The definition of uniform consistency is akin to one in subsection 2.3.

In the following Theorem we consider the boundedness and compactness for
Hilbert-Schmidt norm.

###### Theorem 2.6

Let $U$ be bounded convex set and let $A_{0}$ be internal point of $U$. Then
there is $\rho_{\varepsilon}\to 0$ as $\varepsilon\to 0$ such that sets of
alternatives $V(\rho_{\varepsilon})$ are uniformly consistent, if and only if,
the set $U$ is relatively compact.

The reasoning are akin to proof of Theorem 2.1. It suffices only to implement
Theorem 5.7 in [5].

##  3 Proof of Theorem 2.1

Suppose that there is uniformly consistent sequence of alternatives
$V(\rho_{n})$, $\rho_{n}\to 0$ as $n\to\infty$. Then we implement Theorem 2.2
and point out compact set $W$ such that $U\subset W$.

Fix $\varepsilon_{1}>0$. For each $i>1$, we put
$\varepsilon_{i}=\frac{\varepsilon_{i-1}}{2}$.

By Theorem 2.2, for each $i$, there are functions
$g_{i1},\ldots,g_{ik_{i}}\in\mathbb{L}_{q}$, $\|g_{ij}\|_{q}=1$ for $1\leq
j\leq k_{i}$, $\frac{1}{p}+\frac{1}{q}=1$, and constants
$c_{i1},\ldots,c_{ik_{i}}$ such that

$V(\varepsilon_{i})\subset\cup_{l=1}^{i}\cup_{j=1}^{k_{l}}\Pi(g_{lj},c_{lj})$
(3.1)

and

$0\notin\cup_{l=1}^{i}\cup_{j=1}^{k_{l}}\Pi(g_{lj},c_{lj}),$ (3.2)

where

$\Pi(g_{lj},c_{lj})=\Bigl{\\{}\,f\,:\,\int_{S}g_{lj}\,f\,d\,\mathbf{P}_{0}>c_{lj},f\in\mathbb{L}_{p}\Bigr{\\}}.$

Denote $\Gamma(g_{lj},c_{lj})$ the boundary hyperplane of
$\Pi(g_{lj},c_{lj})$.

Define sets $G_{i}=\\{g_{i1},\ldots,g_{ik_{i}}\\}$, $1\leq i<\infty$.

It is clear, that we can suppose additionally that, if $g\in G_{i}$, then
$-g\in G_{i}$, $1\leq i<\infty$. Otherwise we can add such functions.
Moreover, we can suppose that, if $g_{ij_{1}}=-g_{ij_{2}}$, $1\leq j_{1}\neq
j_{2}\leq k_{i}$, then $c_{ij_{1}}=c_{ij_{2}}$.

We can also suppose that $g_{ij}$ are step functions and therefore
$g_{ij}\in\mathbb{L}_{p}\cap\mathbb{L}_{q}$, $1\leq j\leq k_{i}$, $1\leq
i<\infty$. Otherwise we can replace functions functions $g_{ij}$ by their step
approximations and change constants $c_{ij}$ insignificantly. We can also
choose functions $g_{ij}$ such that function $g_{i_{1}j_{1}}$ is orthogonal to
function $g_{i_{2},j_{2}}$ in $\mathbb{L}_{2}$, for any $1\leq i_{1}\neq
i_{2}<\infty$ and for any $1\leq j_{1}<k_{i_{1}}$, $1\leq j_{2}<k_{i_{2}}$.
Suppose also that $\|g_{ij}\|_{q}=1$ for $1\leq j\leq k_{i}$, $1n\leq
i<\infty$.

For $i$, $1\leq i<\infty$, denote $M_{i}$ linear subspace generated functions
$g_{i1},\ldots,g_{ik_{i}}$.

Denote $B(M_{i},\rho)$ ball in subspace $M_{i}$ of $\mathbb{L}_{p}$ having
center zero and radius $\rho>0$.

Denote
$\Omega_{i}=M_{i}\cap\cap_{j=1}^{k_{i}}\bar{\Pi}(g_{ij},\varepsilon_{i-1})$

Fix $\delta>0$. We can take the number of functions $g_{ij}$,
$\|g_{ij}\|_{q}=1$, $1\leq j\leq k_{i}$, so large that, for any
$f\in\Omega_{i}$, we have

$\|f\|_{p}<\frac{\varepsilon_{i-1}}{1-\delta}.$ (3.3)

Denote $d_{i}\doteq\frac{\varepsilon_{i-1}}{1-\delta}$.

For definition of set $W$ we implement induction by $i$.

Since set $U$ is bounded there is $d_{1}$ such that for any $j$, $1\leq j\leq
k_{1}$, and, for any $f\in U$, we have $f\in\bar{\Pi}(g_{1j},d_{1})$ where
$\bar{\Pi}(g_{1j},d_{1j})=\mathbb{L}_{p}\setminus\Pi(g_{1j},d_{1})$.

Let $v\in U\setminus B_{\varepsilon_{1}}(0)$,
$\int_{S}g_{11}vd\,\mathbf{P}_{0}>c_{11}$, and let $v$ be bounded function.
Then there is $\lambda<0$ such that $h\doteq\lambda v\in U$ and $1+\lambda v$
is a density.

Denote
$\Pi_{0}=\Bigl{\\{}\,f\,:\,\int_{S}g_{11}fd\,\mathbf{P}_{0}>0,f\in\mathbb{L}_{p}\Bigr{\\}}$.
Let $\Gamma_{0}$ be the boundary hyperplane of $\Pi_{0}$.

Denote $W_{1}=\cap_{j=1}^{k_{1}}\bar{\Pi}(g_{1j},d_{1})$.

Let $i>1$. For each $j$, $1\leq j\leq k_{i}$, we draw hyperplane
$\Upsilon_{ij}$ passing through the point $h$ and
$\Gamma(g_{ij},d_{i})\cap\Gamma_{0}$. Denote $\Psi_{i,j}$ the set having
hyperplane $\Upsilon_{i,j}$ as a boundary and containing $(U\setminus
B(\varepsilon_{i-1}))\cap\Pi_{0}$.

Denote $W_{i}=\cap_{j=1}^{k_{i}}\Psi_{ij}\cap W_{i-1}$.

Then $U\cap\Pi_{0}\subset W_{i}$.

Denote $L_{i}$ linear space generated functions from linear spaces
$M_{1},\ldots,M_{i}$.

Let $R>0$ be such that $U\subset B_{R}(0)$.

Using triangle similarity considerations and (3.3), we have

$\begin{split}&\sup_{f}\,\,\,\inf_{f_{1}}\,\,\\{\|f-f_{1}\|_{p}\,:\,f\in\Upsilon_{i,j}\cap
W_{i}\cap L_{i},\,\,f_{1}\in W_{i-1}\cap L_{i-1}\,\\}\\\
&\leq|\lambda|^{-1}R\,\sup_{f}\\{\|f-f_{1}\|_{p}\,:\,f\in\Upsilon_{i,j}\cap
W_{i}\cap L_{i}\cap\Gamma_{0},f_{1}\in W_{i-1}\cap L_{i-1}\cap\Gamma_{0}\\}\\\
&\leq d_{i}|\lambda|^{-1}R.\end{split}$ (3.4)

for any $i$, $1<i<\infty$, and any $j$, $1\leq j\leq k_{i}$.

Denote $W$ the closure of $\cap_{i=1}^{\infty}W_{i}$. By (3.4), $n$-width of W
tends to zero, therefore $W$ is relatively compact. Since $U\cap\Pi_{0}\subset
W$ then $U\cap\Pi_{0}$ is relatively compact as well. The case
$U\setminus\Pi_{0}$ is explored similarly.

## References

  * [1] Birge, L. Robust tests for model selection. IMS Collections 9 (2012), 4764.
  * [2] Burnashev, M.V. (1979). On the minimax solution of inaccurately known signal in a white Gaussian noise . Background. Theory Probab.Appl. 24 107-119.
  * [3] Dembo, A. and Peres, Y. (1994) A topological criterion for hypothesis testing. Ann.Statist. 22 106-117.
  * [4] H. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers (1996).
  * [5] M.S. Ermakov, "On consistent hypothesis testing," J. Math. Sci. (NY), 225 751-769 (2017).
  * [6] Ermakov M.S. (2020) On Asymptotically Minimax Nonparametric Detection of Signal in Gaussian White Noise Journal of Mathematical Sciences, 251(1), 78-87 DOI 10.1007/s10958-020-05067-7
  * [7] Ermakov M S (2021) On Uniform consistency of nonparametric tests I. Journal of Mathematical Sciences,v 258 802-837
  * [8] Ganssler, P.(1971). Compactness and sequential compactness on the space of measures. Z.Wahrsch.Verw. Gebiete 17 124-146.
  * [9] I.A. Ibragimov and R.Z. Khasminskii, "On the estimation of infinitely dimensional parameter in Gaussian white noise," Dokl.AN USSR 236 1053-1055 (1977).
  * [10] Hoeffding, W and Wolfowitz, J.(1958). Distinguishability of sets of distributions. Ann.Math.Stat. 29 700-718.
  * [11] Ingster Yu. I., Asymptotically minimax hypothesis testing for nonparametric alternatives. I, II, III, Mathematical Methods of Statistics, 2 (1993), 85–114, 171–189, 249–268.
  * [12] Ingster, Yu. I. and Kutoyants, Yu.A.(2007). Nonparametric hypothesis testing for intensity of the Poisson process.Mathematical Methods of Statistics, 16 218–246.
  * [13] Ingster, Yu.I., Suslina I.A. (2002). Nonparametric Goodness-of-fit Testing under Gaussian Models. Lecture Notes in Statistics 169 Springer N.Y.
  * [14] Janssen, A. (2000). Global power function of goodness of fit tests. Annals of Statistics, 28 239-253.
  * [15] Kraft, C. (1955). Some conditions for consistency and uniform consistency of statistical procedures. Univ.Californ.Publ.Stat. 2 125-142.
  * [16] Le Cam, L. (1973). Convergence of estimates under dimensionality restrictions. Ann.Statist. 1 38-53.
  * [17] L. Le Cam and L. Schwartz, "A necessary and sufficient conditions for the existence of consistent estimates," Ann.Math.Statist. 31 140-150 (1960).
  * [18] Pfanzagl, J. (1968). On the existence of consistent estimates and tests. Z.Wahrsch.Verw. Gebiete 10 43-62.
  * [19] M. J. Wainwright, High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
  * [20] Y. Wei and M. J. Wainwright. The local geometry of testing in ellipses: Tight control via localized kolmogorov widths. IEEE Transactions on Information Theory, 66(8):51105129, 2020.