# Broadband switchable terahertz half-/quarter-wave plate based on VO2-metal
hybrid metasurface with over/underdamped transition

Xiaoqing Luo1,2, Fangrong Hu3, and Guangyuan Li1,2,4,∗

###### Abstract

Dynamically switchable half-/quarter-wave plates have recently been the focus
in the terahertz regime. Conventional design philosophy leads to multilayer
metamaterials or narrowband metasurfaces. Here we propose a novel design
philosophy and a VO2-metal hybrid metasurface for achieving broadband
dynamically switchable half-/quarter-wave plate (HWP/QWP) based on the
transition from the overdamped to the underdamped resonance. Results show
that, by varying the VO2 conductivity by three orders of magnitude, the
proposed metasurface’s function can be switched between an HWP with
polarization conversion ratio larger than 96% and a QWP with ellipticity close
to $-1$ over the broad working band of 0.8–1.2 THz. We expect that the
proposed design philosophy will advance the engineering of metasurfaces for
dynamically switchable functionalities beyond the terahertz regime.

1CAS Key Laboratory of Human-Machine Intelligence-Synergy Systems, Shenzhen
Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen,
518055 China

2Guangdong-Hong Kong-Macao Joint Laboratory of Human-Machine Intelligence-
Synergy Systems, Chinese Academy of Sciences, Shenzhen Institutes of Advanced
Technology, Shenzhen 518055, China

3Guangxi Key Laboratory of Optoelectronic Information Processing, Guilin
University of Electronic Technology, Guilin 541004, China

4Shenzhen College of Advanced Technology, University of Chinese Academy of
Sciences, Shenzhen 518055, China

*Corresponding author<EMAIL_ADDRESS>
Polarization is an important characteristic of electromagnetic waves, and the
manipulation of the polarization is desirable in a diverse range of
applications, such as sensing, imaging, encryption, and communications [1].
Conventional approaches based on birefringence or total internal reflection
effects are usually bulky and narrowband, and sometimes lossy. To circumvent
these problems, metamaterials and their two-dimensional counterparts,
metasurfaces, have recently been extensively explored because of their
appealing merits such as compactness, high efficiency, broad bandwidth and
easy integration [1, 2, 3, 4].

In the terahertz regime, metamaterial- or metasurface-based polarization
converters, especially HWPs and QWPs, are of particular interest due to the
lack of suitable natural materials. Over the years, these terahertz
metadevices have evolved from narrowband [5] to broadband [6], and from
untunable to actively reconfigurable [7, 8, 9]. For example, based on
metamaterials or metasurfaces that are made of metals or dielectrics,
broadband terahertz HWPs [10, 11, 12] or QWPs [13, 14, 15, 11, 16] have been
proposed or demonstrated. Quite recently, dynamically switchable HWPs/QWPs
based on metamaterials or metasurfaces incorporating tunable materials such as
graphene [17, 18, 19, 20] or VO2 [21, 22, 23, 24] have received increasing
attention.

Although the structures for terahertz switchable HWP/QWP, as well as for other
switchable bi-functionalities, such as switchable HWP and perfect absorber
[25], or switchable on/off asymmetric transmission [26], may be distinct in
the literature, the design philosophy is almost the same. One first treats
graphene with small Fermi level (or VO2 in the insulating state at low
temperature) as transparent dielectric because of the low conductivity, and
design metal structures for one functionality such as HWP without considering
graphene (or VO2). For graphene with high Fermi level (or VO2 in the
conducting state at high temperature), the conductivity is as high as metal-
like material, such that one can approximately treat graphene (or VO2) as
metal and then add graphene (or VO2) structures to the metal structures for
the other functionality such as QWP. This design philosophy usually results in
metamaterials composed of stacked multilayer structures, complicating the
fabrication and thus hindering the practical applications. A typical example
is our previous design for achieving broadband switchable HWP/QWP [23], where
the metal structures function as a broadband HWP while the VO2 structures act
as a broadband QWP.

Following the above design philosophy, there exist a few exceptions [21, 22,
20], which are planar metasurfaces, greatly facilitating the fabrication
compared with the multilayer metamaterials. However, their bandwidths are
extremely narrow. For example, the switchable QWP based on a VO2-metal hybrid
metasurface works at only one [21] or two specific frequencies [22], and the
switchable HWP/QWP based on a graphene-dielectric hybrid metasurface has
narrow bandwidth of 0.1 THz around 1 THz [20]. In other words, it remains
challenging to design a broadband switchable HWP/QWP based on the metasurface.

In this letter, we propose a VO2-metal hybrid metasurface for achieving
broadband switchable HWP/QWP in the terahertz regime. This metasurface is
designed following a novel philosophy based on the transition from the
overdamped to the underdamped resonance. We will show that by varying the VO2
conductivity by three orders of magnitude, which can be done through thermal,
optical or electrical stimulus [27], the proposed metasurface functions as a
switchable HWP/QWP with high efficiencies over a broad band of 0.8–1.2 THz.

Based on Jones matrix and Poincaré sphere analyses, Ma et al. [11] developed a
set of general criteria to design high-efficiency broadband terahertz
waveplates using reflective metasurfaces:

$|r_{xx}|\approx|r_{yy}|\approx 1,\quad\&\quad{\rm arg}(r_{yy})-{\rm
arg}(r_{xx})=180^{\circ}\,,$ (1)

for an HWP, and for a QWP,

$|r^{\prime}_{xx}|\approx|r^{\prime}_{yy}|\approx 1,\quad\&\quad{\rm
arg}(r^{\prime}_{yy})-{\rm arg}(r^{\prime}_{xx})=\pm 90^{\circ}\,.$ (2)

Here $r_{xx}$ and $r_{yy}$ (or $r^{\prime}_{xx}$ and $r^{\prime}_{yy}$) are
the reflection coefficients for the $\vec{E}\parallel\hat{x}$ and
$\vec{E}\parallel\hat{y}$ polarizations, respectively, and the sign “$+/-$”
denotes right- or left-circular final polarization state.

Therefore, in order to realize a metasurface that can be switched from an HWP
to a QWP, here we propose a novel design philosophy. We first design a
metal/insulator/metal (MIM) configuration with $r_{xx}$ working in the
underdamped regime whereas $r_{yy}$ in the overdamped regime, such that all
the reflection coefficients have near-unitary amplitude, indicating low
absorption, and that $r_{xx}$ can exhibit a 360∘ reflection phase coverage as
frequency varies. This can lead to a high performance HWP according to Eq.
(1). As the conductivity of VO2 (or graphene) $\sigma$ increases, $r_{xx}$
remains unchanged so that

$|r^{\prime}_{xx}|\approx|r_{xx}|,\quad\&\quad{\rm
arg}(r^{\prime}_{xx})\approx{\rm arg}(r_{xx})\,,$ (3)

and meanwhile $r_{yy}$ transits from the overdamped to the underdamped regime
so that

${\rm arg}(r^{\prime}_{yy})-{\rm arg}(r_{yy})=-270^{\circ}\,.$ (4)

Satisfying Eqs. (3) and (4) when $\sigma$ increases will result in dynamic
switching from an HWP to a QWP. In other words, the metasurface initially has
an underdamped and an overdamped resonances for two orthogonal polarizations,
leading to an HWP, and as $\sigma$ increases the overdamped resonance transits
into an underdamped resonance, resulting in a QWP.

Figure 1: (a)–(c) Schematics of the proposed VO2-metal hybrid metasurface for
achieving broadband switchable terahertz HWP/QWP. Geometric parameters used in
this work are $\Lambda_{x}=162\leavevmode\nobreak\ \mu$m,
$\Lambda_{y}=120\leavevmode\nobreak\ \mu$m, $h=33\leavevmode\nobreak\ \mu$m,
$L_{x}=95\leavevmode\nobreak\ \mu$m, $L_{y}=80\leavevmode\nobreak\ \mu$m,
$w_{x}=18\leavevmode\nobreak\ \mu$m, $w_{y}=8\leavevmode\nobreak\ \mu$m,
$g=6\leavevmode\nobreak\ \mu$m. VO2-gold hybrid structures have thickness of
200 nm. (d) Smith curves of the reflection coefficients $r$ for different VO2
conductivities. Red, black, and blue curves represent underdamped, critical
damped, and overdamped behaviors, respectively. The arrows indicate $f$
increasing from 0 to $\infty$.

Following our design philosophy, we propose a VO2-gold hybrid metasurface for
achieving switchable HWP/QWP, as illustrated by Figure 1. The proposed
metasurface is composed of two gold crosses bridged by a VO2 short stripe, all
of which stand on a gold mirror sandwiched by a polyimide spacer of thickness
$h$. The metasurface can be fabricated using standard bottom-up processes. A
thick gold film is first evaporated onto a substrate, followed by spin-coating
of a polyimide spacer. A thin film of VO2 is then deposited and is patterned
using photolithography and etching. Finally, the gold crosses are patterned
through photolithography, evaporation and lift-off processes.

The polarization-dependent reflection resonance characteristics as well as the
near-field distributions were numerically simulated using the frequency-domain
solver in CST Microwave Studio. The reflection coefficients were obtained with
$r_{xx}=S_{11}$ and $r_{yy}=S_{22}$. We modelled gold using the lossy metal
model with conductivity of $4.56\times 10^{7}$ S/m, and set the relative
permittivity of the polyimide to be $\varepsilon_{\rm
PI}=3.5\times(1+0.0027i)$. We adopted Drude model to describe the frequency-
dependent permittivities of VO2 [28]:
$\varepsilon(\omega)=\varepsilon_{\infty}-\omega_{\rm
p}^{2}(\sigma)/(\omega^{2}+i\gamma\omega)$, where $\varepsilon_{\infty}$ is
the permittivity at high frequency limit, $\omega_{\rm
p}(\sigma)=\sqrt{\sigma/\sigma_{0}}\omega_{\rm p}(\sigma_{0})$ is the
conductivity-dependent plasmon frequency, $\sigma$ is the conductivity,
$\omega_{\rm p}(\sigma_{0})=1.4\times 10^{15}$ rad/s for $\sigma_{0}=3\times
10^{5}$ S/m, and $\gamma=5.75\times 10^{13}$ rad/s is the collision frequency.

Figure 2: (a) Reflectance $|r_{yy}|^{2}$ and (b) reflection phase ${\rm
arg}(r_{yy})$ spectra for different VO2 conductivities.

We first examine the dynamic transition from the overdamped to the underdamped
regime for $r_{yy}$, as the VO2 conductivity increases from $\sigma=200$ S/m
to $2\times 10^{5}$ S/m. Fig. 2(a) shows that for $\sigma=200$ S/m, the
reflectance slightly decreases as frequency increases. As the conductivity
increases, a pronounced reflectance dip around 0.67 THz first becomes deeper
and closer to zero reflectance, and then becomes shallower. Correspondingly,
the reflectance phase variation is less than 180∘ across the resonance
frequency for small conductivities of $\sigma\lesssim 2.8\times 10^{4}$ S/m.
In other words, $r_{yy}$ is in the overdamped regime with $\Gamma_{\rm
rad}<\Gamma_{\rm abs}$ and the Smith curve not enclosing the origin [29, 30],
as illustrated by Fig. 1(d). For larger conductivities, the phase variation
undergoes a full 360∘ range. This is because the resonance is now in the
underdamped regime, for which $\Gamma_{\rm rad}>\Gamma_{\rm abs}$ and the
Smith curve encloses the origin [29, 30]. A transition from the overdamped to
the overdamped regime occurs at $\sigma\approx 2.8\times 10^{4}$ S/m. In this
scenario, the reflectance at the resonance frequency is close to zero and the
phase variation changes abruptly from less than 180∘ to 360∘.

Remarkably, the dynamic reflectance phase modulation can reach as high as 358∘
if the VO2 conductivity varies from $\sigma=2\times 10^{3}$ S/m to $3\times
10^{4}$ S/m, only by 15 times. If we vary $\sigma$ by three orders of
magnitude, from 200 S/m to $2\times 10^{5}$ S/m, the phase modulation reaches
285∘, which is very close to 270∘ as required for switching an HWP to a QWP
according to Eq. (4). More interestingly, in Fig. 2 we notice that, within the
wide spectral band of 0.8–1.2 THz, $|r_{yy}|^{2}\approx 0.9$ for both
$\sigma=200$ S/m and $\sigma=2\times 10^{5}$ S/m, and their phase variations
across the resonance frequency are nearly parallel to each other,
corresponding to nearly constant phase modulation of $285^{\circ}$. This
suggests broad bandwidth for the designed switchable HWP/QWP.

Figure 3: Reflection (a) amplitude and (b) phase spectra for $r_{xx}$ and
$r_{yy}$ with $\sigma=200$ S/m and $2\times 10^{5}$ S/m. Blue region suggests
the bandwidth of the switchable HWP/QWP.

Having verified Eq. (4), we now examine whether Eqs. (1) and (3) can also be
satisfied. Fig. 3 shows that for both $\sigma=200$ S/m and $\sigma=2\times
10^{5}$ S/m, both the amplitude and the phase of $r_{xx}$ remain unchanged,
and $|r_{xx}|\approx 0.98$, consistent with our design philosophy. There
exists a weak reflectance dip around 0.78 THz for $r_{xx}$, and the
corresponding phase variation across the resonance frequency covers the full
range of 360∘. This indicates that the resonance of $r_{xx}$ is in the
underdamped regime. By carefully optimizing the geometric parameters of the
proposed metasurface, we can tune the phase variation across the resonance
frequency for $r_{xx}$ such that it locates between those for $r_{yy}$ with
$\sigma=200$ S/m and with $\sigma=2\times 10^{5}$ S/m, and that the phase
differences within 0.8–1.2 THz are $\sim 180^{\circ}$ for $\sigma=200$ S/m,
and $\sim 90^{\circ}$ for $\sigma=2\times 10^{5}$ S/m, as shown by Fig. 3(b).
In other words, Eqs. (1) and (2) are approximately satisfied over a broad
band. Therefore, we expect that, by varying the VO2 conductivity between
$\sigma=200$ S/m and $2\times 10^{5}$ S/m, the function of the designed
metasurface can be dynamically switched between an HWP and a QWP within the
broad band of 0.8–1.2 THz.

To understand the distinct resonance characteristics of the proposed
metasurface with different VO2 conductivities and under the two orthogonal
polarizations, we plot the surface current maps and the magnetic field
distributions in Fig. 4. Under the $\vec{E}\parallel\hat{y}$ polarization at
$f=0.67$ THz, the surface currents and the magnetic fields are very weak for
$\sigma=200$ S/m, consistent with the indistinct resonance in the reflectance
spectra in Fig. 2(a). For $\sigma=2.8\times 10^{4}$ S/m, there exist a
clockwise and an counterclockwise currents on the VO2-gold hybrid structures’
top surface. The magnetic field is mainly confined to the hybrid structures.
This corresponds to the critical transition point between the overdamped and
underdamped regimes. For $\sigma=2\times 10^{5}$ S/m, the clockwise and
counterclockwise currents are relatively weak, whereas the upward-propagating
surface currents on the hybrid structures and those propagating downwards on
the gold film are strong. This corresponds to extremely strong magnetic field
in the overcoupled MIM cavity. Therefore, as $\sigma$ increases from 200 S/m
to $2\times 10^{5}$ S/m, $r_{yy}$ undergoes a transition from the overdamped
to the underdamped regime. However, under the $\vec{E}\parallel\hat{x}$
polarization at $f=0.78$ THz, the surface currents mainly propagate rightwards
on the hybrid structures and leftwards on the gold film, and the corresponding
magnetic field is strong in the overcoupled MIM cavity, irrespective of
whether $\sigma=200$ S/m or $2\times 10^{5}$ S/m. In other words, $r_{xx}$
stays in the underdamped regime for both conductivities.

Figure 4: From left to right: surface current maps on the hybrid structures
and the gold film, and magnetic field maps $H_{x}$ in the $y-z$ plane with the
spacer layer outlined by purple lines. From top to bottom: $\sigma=200$ S/m,
$2.8\times 10^{4}$ S/m, and $2\times 10^{5}$ S/m under
$\vec{E}\parallel\hat{y}$ polarization at 0.67 THz, and $\sigma=200$ S/m or
$2\times 10^{5}$ S/m under $\vec{E}\parallel\hat{x}$ polarization at 0.78 THz.

We now rotate the sample along the $z$-axis by an angle of 45∘, as illustrated
by Fig. 1(c), and simulate the polarization conversion performance of the
obtained switchable HWP/QWP. We adopt the polarization conversion ratio, ${\rm
PCR}\equiv|r_{vu}|^{2}/(|r_{vu}|^{2}+|r_{uu}|^{2})$, and the degree of linear
polarization, ${\rm
DoLP}=\sqrt{\left(|r_{uu}|^{2}-|r_{vu}|^{2})^{2}+(2|r_{vu}||r_{uu}|\cos(\Delta\Phi)\right)^{2}}/(|r_{vu}|^{2}+|r_{uu}|^{2})$
to quantify the HWP, and adopt the ellipticity $\chi=S_{3}/S_{0}$ to quantify
the QWP. Here, $\Delta\Phi={\rm arg}(r_{vu})-{\rm arg}(r_{uu})$ is the phase
difference, $S_{3}=2|r_{vu}||r_{uu}|\sin(\Delta\Phi)$ and
$S_{0}=|r_{vu}|^{2}+|r_{uu}|^{2}$ are the Stokes parameters.

Figure 5: (a) Simulated spectra of co- and cross-polarization reflectance
amplitudes, and (b) of PCR and DoLP for the HWP obtained when $\sigma=200$
S/m. (c) Simulated spectra of phase differences and (c) of ellipticity for the
QWP obtained when $\sigma=2\times 10^{5}$ S/m. Blue regions define the working
bandwidth.

When the proposed metasurface acts as an HWP for $\sigma=200$ S/m, Fig. 5(a)
shows that the cross-polarization reflection amplitude $|r_{vu}|\approx 0.96$,
whereas the co-polarization response $|r_{uu}|<0.2$ within 0.8–1.2 THz.
Correspondingly, ${\rm PCR}>0.96$ and ${\rm DoLP}>0.94$, as shown by Fig.
5(b). These imply that the incident $u$-polarization wave is efficiently
converted to the reflective $v$-polarization wave. When the proposed
metasurface acts as a QWP for $\sigma=2\times 10^{5}$ S/m, Figs. 5(c)(d) show
that, the phase difference is around 90∘ and the ellipticity is close to $-1$
within the same spectral band. This suggests that the incident
$u$-polarization wave is efficiently converted to the reflective left-handed
circularly polarized wave. Both the HWP and the QWP share the same band with
the central frequency locating at 1 THz and the relative bandwidth reaching
40%, which is four times of the metasurface in [20]. Therefore, the proposed
metasurface can function as a broadband and high-efficiency HWP or QWP by
varying the VO2 conductivity.

In conclusion, we have proposed a novel design philosophy and a VO2-metal
metasurface for achieving a broadband switchable terahertz HWP/QWP. Results
have shown that by varying the VO2 conductivity from 200 S/m to $2\times
10^{5}$ S/m, $r_{xx}$ remains in the underdamped regime whereas $r_{yy}$
undergoes a transition from the overdamped to the underdamped regime.
Therefore, when $\sigma=200$ S/m, $r_{xx}$ can exhibit a 360∘ reflection phase
coverage as frequency varies and thus Eq. (1) can be satisfied, resulting in a
high-performance HWP; when $\sigma$ raises to $2\times 10^{5}$ S/m, $r_{xx}$
is unchanged but $r_{yy}$ obtains phase modulation of $\sim 270^{\circ}$,
satisfying Eqs. (3) and (4) and leading to a high-performance QWP. Simulations
results have shown that for the obtained HWP, the PCR is greater than 0.96 and
the DoLP is larger than 0.94, while for the obtained QWP, the phase difference
is around $-90^{\circ}$ and the ellipticity is close to $-1$, and that the
working bandwidth of the switchable HWP/QWP covers 0.8–1.2 THz. We expect the
proposed design philosophy will advance the design of reconfigurable
metasurfaces for switchable functionalities beyond the terahertz regime.

## Acknowledgments

This work was supported by Shenzhen Fundamental Research and Discipline Layout
project (JCYJ20180507182444250) and China Postdoctoral Science Foundation
(2020M682984).

## References

  * [1] Jia-ming Hao, Min Qiu, and Lei Zhou.  Manipulate light polarizations with metamaterials: From microwave to visible.  Front. Phys. China, 5(3):291–307, 2010.
  * [2] Hou-Tong Chen, Antoinette J Taylor, and Nanfang Yu.  A review of metasurfaces: physics and applications.  Rep. Prog. Phys., 79(7):076401, 2016.
  * [3] Shuqi Chen, Zhancheng Li, Wenwei Liu, Hua Cheng, and Jianguo Tian.  From single-dimensional to multidimensional manipulation of optical waves with metasurfaces.  Adv. Mater., 31:1802458, 2019.
  * [4] Yuttana Intaravanne and Xianzhong Chen.  Recent advances in optical metasurfaces for polarization detection and engineered polarization profiles.  Nanophotonics, 9(5):1003–1014, 2020.
  * [5] Xomalin G. Peralta, Evgenya I. Smirnova, Abul K. Azad, Hou-Tong Chen, Antoinette J. Taylor, Igal Brener, and John F. O’Hara.  Metamaterials for thz polarimetric devices.  Opt. Express, 17:773–783, 2009.
  * [6] Nathaniel K Grady, Jane E Heyes, Dibakar Roy Chowdhury, Yong Zeng, Matthew T Reiten, Abul K Azad, Antoinette J Taylor, Diego AR Dalvit, and Hou-Tong Chen.  Terahertz metamaterials for linear polarization conversion and anomalous refraction.  Science, 340(6138):1304–1307, 2013.
  * [7] Shuyuan Xiao, Tao Wang, Tingting Liu, Chaobiao Zhou, Xiaoyun Jiang, and Jianfa Zhang.  Active metamaterials and metadevices: a review.  J. Phys. D: Appl. Phys., 53:503002, 2020.
  * [8] Qiong He, Shulin Sun, and Lei Zhou.  Tunable/reconfigurable metasurfaces: physics and applications.  Research, 2019:1849272, 2019.
  * [9] Lei Bao and Tie Jun Cui.  Tunable, reconfigurable, and programmable metamaterials.  Microw. Opt. Technol. Lett., 62(1):9–32, 2020.
  * [10] Y. Cheng, W. Withayachumnankul, A. Upadhyay, Yan Nie, Rong Zhou Gong, Madhu Bhaskaran, Sharath Sriram, and Derek Abbott.  Ultrabroadband reflective polarization convertor for terahertz waves.  Appl. Phys. Lett., 105:181111, 2014.
  * [11] Shaojie Ma, Xinke Wang, Weijie Luo, Shulin Sun, Yan Zhang, Qiong He, and Lei Zhou.  Ultra-wide band reflective metamaterial wave plates for terahertz waves.  EPL, 117(3):37007, 2017.
  * [12] Rui Xia, Xufeng Jing, Xincui Gui, Ying Tian, and Zhi Hong.  Broadband terahertz half-wave plate based on anisotropic polarization conversion metamaterials.  Opt. Mater. Express, 7(3):977–988, 2017.
  * [13] Longqing Cong, Ningning Xu, Jianqiang Gu, Ranjan Singh, Jiaguang Han, and Weili Zhang.  Highly flexible broadband terahertz metamaterial quarter-wave plate.  Laser Photonics Rev., 8(4):626–632, 2014.
  * [14] Muhammad Tayyab Nouman, Ji Hyun Hwang, and Jae-Hyung Jang.  Ultrathin terahertz quarter-wave plate based on split ring resonator and wire grating hybrid metasurface.  Sci. Rep., 6(1):39062, 2016.
  * [15] TIANJING Guo and CHRISTOS Argyropoulos.  Broadband polarizers based on graphene metasurfaces.  Opt. Lett., 41:5592–5595, 2016.
  * [16] Wendy SL Lee, Rajour T Ako, Mei Xian Low, Madhu Bhaskaran, Sharath Sriram, Christophe Fumeaux, and Withawat Withayachumnankul.  Dielectric-resonator metasurfaces for broadband terahertz quarter-and half-wave mirrors.  Opt. Express, 26(11):14392–14406, 2018.
  * [17] Wei Zhang, Jianli Jiang, Jing Yuan, Shuang Liang, Jisong Qian, Jing Shu, and Liyong Jiang.  Functionality-switchable terahertz polarization converter based on a graphene-integrated planar metamaterial.  OSA Continuum, 1(1):124–135, 2018.
  * [18] Yun-Yun Ji, Fei Fan, Xiang-Hui Wang, and Sheng-Jiang Chang.  Broadband controllable terahertz quarter-wave plate based on graphene gratings with liquid crystals.  Opt. Express, 26(10):12852–12862, 2018.
  * [19] Mohammad Reza Tavakol, Babak Rahmani, and Amin Khavasi.  Terahertz quarter wave-plate metasurface polarizer based on arrays of graphene ribbons.  IEEE Photon. Technol. Lett., 31:931–934, 2019.
  * [20] Shengnan Guan, Jierong Cheng, Tiehong Chen, and Shengjiang Chang.  Bi-functional polarization conversion in hybrid graphene-dielectric metasurfaces.  Opt. Lett., 44:5683–5686, 2019.
  * [21] Dacheng Wang, Lingchao Zhang, Yinghong Gu, MQ Mehmood, Yandong Gong, Amar Srivastava, Linke Jian, T Venkatesan, Cheng-Wei Qiu, and Minghui Hong.  Switchable ultrathin quarter-wave plate in terahertz using active phase-change metasurface.  Sci. Rep., 5(1):15020, 2015.
  * [22] Dacheng Wang, Lingchao Zhang, Yandong Gong, Linke Jian, T. Venkatesan, Cheng-Wei Qiu, and Minghui Hong.  Multiband switchable terahertz quarter-wave plates via phase-change metasurfaces.  IEEE Photon. J., 8:5500308, 2016.
  * [23] Juan Luo, Xingzhe Shi, Xiaoqing Luo, Fangrong Hu, and Guangyuan Li.  Broadband switchable terahertz half-/quarter-wave plate based on metal-vo 2 metamaterials.  Opt. Express, 28(21):30861–30870, 2020.
  * [24] Zhao Jian-Xing, Song Jian-Lin, Zhou Yao, Liu Yi-Chao, and Zhou Jian-Hong.  Switching between the functions of half-wave plate and quarter-wave plate simply by using a vanadium dioxide film in a terahertz metamaterial.  Chin. Phys. Lett., 37(6):64204, 2020.
  * [25] Fei Ding, Shuomin Zhong, and Sergey I Bozhevolnyi.  Vanadium dioxide integrated metasurfaces with switchable functionalities at terahertz frequencies.  Adv. Opt. Mater., 6(9):1701204, 2018.
  * [26] Xiaoxiang Dong, Xiaoqing Luo, Yixuan Zhou, Yuanfu Lu, Fangrong Hu, Xinlong Xu, and Guangyuan Li.  Switchable broadband and wide-angular terahertz asymmetric transmission based on a hybrid metal-vo2 metasurface.  Opt. Express, 28(21):30675–30685, 2020.
  * [27] Z. Shao, X. Cao, H. Luo, and P. Jin.  Recent progress in the phase-transition mechanism and modulation of vanadium dioxide materials.  NPG Asia Mater., 10:581–605, 2018.
  * [28] Shengxiang Wang, Lei Kang, and Douglas H Werner.  Hybrid resonators and highly tunable terahertz metamaterials enabled by vanadium dioxide VO2.  Sci. Rep., 7:4326, 2017.
  * [29] Che Qu, Shaojie Ma, Jiaming Hao, Meng Qiu, Xin Li, Shiyi Xiao, Ziqi Miao, Ning Dai, Qiong He, Shulin Sun, and Lei Zhou.  Tailor the functionalities of metasurfaces based on a complete phase diagram.  Phys. Rev. Lett., 115:235503, 2015.
  * [30] Ziqi Miao, Qiong Wu, Xin Li, Qiong He, Kun Ding, Zhenghua An, Yuanbo Zhang, and Lei Zhou.  Widely tunable terahertz phase modulation with gate-controlled graphene metasurfaces.  Phys. Rev. X, 5:041027, 2015.


We provide additional views of the different panes in our risk prediction
dashboard that hosts our supported contextual explanations alongside the
different entities that we contextualize, the patient, their risk prediction
and the important features found to contribute to the risk prediction. We also
support interactions between each of these panes which can help clinicians
easily find the content that contextualizes the entities. These interactions
or brushing capabilities include (see Fig. 16, 17, 18):

Figure 16: The risk prediction pane of our risk prediction dashboard, wherein
the risk score is displayed alongside a severity of the score on a threshold
scale.

  * •

Clicking on the patient details pane brings up questions in the questions in
context pane asking about the patient’s diabetes state

  * •

When a month is chosen on the history timeline, questions about a commonly
accepted diabetes indicator, Hemoglobin A1C (HbA1C), are brought up or
filtered in the questions in context pane

  * •

Clicking anywhere in the risk prediction pane brings up questions about the
patient’s predicted risk

  * •

In the feature importances pane, features can be filtered by the selection of
their corresponding, higher-level disease grouping

  * •

Clicking on a feature in the feature importance chart brings up questions
about the feature

  * •

Finally, clicking on a higher-level disease grouping also brings up questions
about the disease grouping

Figure 17: The feature importances pane of our risk prediction dashboard shows
in order of importance the features that contributed to the patient’s
predicted CKD risk. The diagnostic features can also be filtered by their
higher-level disease groupings and can be selected from the filter by column
seen on the left of this figure. Figure 18: Here is the questions in context
pane, which has a list dropdown option as seen on the top of this figure,
where clinicians can browse through the question list we support for the
patient being shown. These questions span the different question types we
support, and the length of the question list is variable depending on how many
diagnostic features contributed to the patient’s predicted risk. Also seen
here is the detail we support for each question and their answer, including
provenance details like the confidence score and the data source for the
predicted answer.


triangle inequality; the third inequality uses Cauchy-Schwarz inequality; and
the last inequality uses (B1) in Lemma 4.1 and (C1) in Lemma 4.3. Denote
$h_{\max}=\max_{i\in[n]}|h_{i}^{(0)}|$. Then we have

$\begin{split}\|w_{j,{\mathtt{T}}}^{(1)}-w_{j}^{(1)}\|&=\frac{\alpha}{n\sqrt{m}}\|\sum_{i=1}^{n}h_{i}^{{(0)}}\phi^{\prime}(\langle
w_{j}^{(0)},x_{i}\rangle)y_{i}x_{i}\|\\\ &\leq\frac{\alpha
h_{\max}}{n\sqrt{m}}\sqrt{\sum_{i=1}^{n}\|x_{i}\|^{2}+n(n-1)\max_{i\neq
j}|x_{i}^{\top}x_{j}|}\\\ &\leq\frac{\alpha
h_{\max}}{n\sqrt{m}}\sqrt{4np}\leq\frac{\sqrt{3}\alpha\omega_{\text{init}}p^{3/2}}{\sqrt{n}},\end{split}$

where the second inequality uses $\|x_{i}\|^{2}\leq 2p$ and $p\geq
Cn^{2}\|\mu\|^{2}$, which come from (B1) and (B2) in Lemma 4.1 and Assumption
(A2) respectively, and the third inequality uses (A.73). Further we have

$\|W_{{\mathtt{T}}}^{(1)}-W^{(1)}\|_{F}=\sqrt{\sum_{j=1}^{m}\|w_{j,{\mathtt{T}}}^{(1)}-w_{j}^{(1)}\|^{2}}\leq\frac{\alpha\omega_{\text{init}}p^{3/2}\sqrt{3m}}{\sqrt{n}}.$

∎

######  Lemma A.11.

Suppose that Assumptions (A1)-(A6) hold. Given
$X\in\mathcal{G}_{\text{data}}$, for each $j\in[m]$, we have

$n/24\leq\text{Var}(D_{+\mu_{1},j}^{(0)})\leq n/2;$
${\mathbb{E}}\big{[}\big{|}D_{+\mu_{1},j}^{(0)})-{\mathbb{E}}[D_{+\mu_{1},j}^{(0)})]\big{|}^{3}\big{]}\leq
n^{3/2}.$

###### Proof.

Recall that
${\mathcal{A}}_{1}={\mathcal{C}}_{+\mu_{1}}\cup{\mathcal{N}}_{-\mu_{1}}$,
${\mathcal{A}}_{2}={\mathcal{C}}_{-\mu_{1}}\cup{\mathcal{N}}_{+\mu_{1}}$.
According to equation (A.17), we have

$D_{+\mu_{1},j}^{(0)}=\sum_{i\in{\mathcal{A}}_{1}}\mathbb{I}(z_{i}>0)-\sum_{i\in{\mathcal{A}}_{2}}\mathbb{I}(z_{i}>0).$
(A.74)

According to Lemma A.15, we have

$\begin{split}\text{Var}(D_{+\mu_{1},j}^{(0)})&={\mathbb{E}}_{B}[f_{1}(b_{1},\cdots,b_{n})]\geq\frac{1}{2}{\mathbb{E}}_{B^{\prime}}[f_{1}(b_{1}^{\prime},\cdots,b_{n}^{\prime})]\\\
&=\frac{1}{2}\text{Var}_{B^{\prime}}(\sum_{i\in{\mathcal{A}}_{1}}b_{i}^{\prime}-\sum_{i\in{\mathcal{A}}_{2}}b_{i}^{\prime})=\frac{|{\mathcal{A}}_{1}|+|{\mathcal{A}}_{2}|}{8}\geq\frac{n}{24},\end{split}$

where
$f_{1}(b_{1},\cdots,b_{n}):=(\sum_{i\in{\mathcal{A}}_{1}}b_{i}-\sum_{i\in{\mathcal{A}}_{2}}b_{i}-(|{\mathcal{A}}_{1}|-|{\mathcal{A}}_{2}|)/2)^{2}\geq
0$, and $b_{i}^{\prime}$ are i.i.d Bernoulli random variables defined in Lemma
A.15, and the last inequality is from (A.16). On the other side, similarly we
have

$\text{Var}(D_{+\mu_{1},j}^{(0)})\leq
2{\mathbb{E}}_{B^{\prime}}[f_{1}(b_{1}^{\prime},\cdots,b_{n}^{\prime})]=(|{\mathcal{A}}_{1}|+|{\mathcal{A}}_{2}|)/2\leq
n/2,$ (A.75)

where the last inequality is from (B3) in Lemma 4.1. Denote
$f_{2}(b_{1},\cdots,b_{n}):=(\sum_{i\in{\mathcal{A}}_{1}}b_{i}-\sum_{i\in{\mathcal{A}}_{2}}b_{i}-(|{\mathcal{A}}_{1}|-|{\mathcal{A}}_{2}|)/2)^{4}\geq
0$, then we have

$\begin{split}{\mathbb{E}}[|D_{+\mu_{1},j}^{(0)}-{\mathbb{E}}[D_{+\mu_{1},j}^{(0)}]|^{4}]&={\mathbb{E}}_{B}[f_{2}(b_{1},\cdots,b_{n})]\leq
2{\mathbb{E}}_{B^{\prime}}[f_{2}(b_{1}^{\prime},\cdots,b_{n}^{\prime})]\\\
&=2{\mathbb{E}}_{B^{\prime}}\big{[}\big{[}\sum_{i\in{\mathcal{A}}_{1}}(b_{i}^{\prime}-\frac{1}{2})-\sum_{i\in{\mathcal{A}}_{2}}(b_{i}^{\prime}-\frac{1}{2})\big{]}^{4}\big{]}\\\
&\leq
16{\mathbb{E}}_{B^{\prime}}\big{[}\big{[}\sum_{i\in{\mathcal{A}}_{1}}(b_{i}^{\prime}-\frac{1}{2})\big{]}^{4}+\big{[}\sum_{i\in{\mathcal{A}}_{2}}(b_{i}^{\prime}-\frac{1}{2})\big{]}^{4}\big{]}\\\
&\leq 4(|{\mathcal{A}}_{1}|^{2}+|{\mathcal{A}}_{2}|^{2})\leq
n^{2},\end{split}$ (A.76)

where the first inequality uses Lemma A.15; the second inequality uses
$(a+b)^{4}\leq 8(a^{4}+b^{4})$; the third inequality uses the formula of the
fourth central moment of a binomial distribution with parameter equal to
$1/2$, i.e. $\mu_{4}(\text{B}(n,1/2))=n(1+(3n-6)/4)/4\leq n^{2}/4$; and the
last inequality is from (B3) in Lemma 4.1. Combining (A.75) and (A.76), we
have

${\mathbb{E}}\big{[}\big{|}D_{+\mu_{1},j}^{(0)})-{\mathbb{E}}[D_{+\mu_{1},j}^{(0)})]\big{|}^{3}\big{]}\leq\sqrt{\text{Var}(D_{+\mu_{1},j}^{(0)}){\mathbb{E}}[|D_{+\mu_{1},j}^{(0)}-{\mathbb{E}}[D_{+\mu_{1},j}^{(0)}]|^{4}]}\leq
n^{3/2}$

by applying the Cauchy-Schwarz inequality.

∎

######  Lemma A.12.

Suppose that Assumptions (A1)-(A6) hold. Given
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathcal{G}_{\text{data}}$, we have

${\mathbb{P}}(\Big{|}\sum_{j=1}^{m}a_{j}\phi(a_{j}D_{+\mu_{1},j}^{(0)})-\frac{1}{2}{\mathbb{E}}[D_{+\mu_{1},j}^{(0)}]\Big{|}>t)\leq
2\bar{\Phi}\big{(}\frac{t\sqrt{m}}{3C_{n}\sqrt{n\varepsilon}}\big{)}+\frac{C}{\sqrt{m}};$
${\mathbb{P}}(\Big{|}\sum_{j=1}^{m}a_{j}|a_{j}D_{+\mu_{1},j}^{(0)}|\Big{|}>t)\leq
2\bar{\Phi}\big{(}\frac{t\sqrt{m}}{3C_{n}\sqrt{n\varepsilon}}\big{)}+\frac{C}{\sqrt{m}}.$

###### Proof.

In this proof, by convention all
${\mathbb{P}}(\cdot),{\mathbb{E}}[\cdot],\text{Var}(\cdot),\rho(\cdot)$ are
implicitly conditioned on a fixed $X$. Denote the expectation of
$D_{+\mu_{1},j}^{(0)}$ by $e_{+\mu_{1}}$. Note that conditioning on $X$,
$\\{a_{j}\phi(a_{j}D_{+\mu_{1},j}^{(0)})\\}_{j\geq 1}$ are i.i.d, and the
expectation of $D_{+\mu_{1},j}^{(0)}$ is

$e_{+\mu_{1}}=(c_{+\mu_{1}}-n_{+\mu_{1}}-c_{-\mu_{1}}+n_{-\mu_{1}})/2\leq
2C_{n}\sqrt{n\varepsilon},$ (A.77)

where the inequality uses (B3) in Lemma 4.1. By Lemma A.11, we have

$\frac{n}{24}\leq\text{Var}\big{(}D_{+\mu_{1},j}^{(0)}\big{)}\leq\frac{n}{2};\quad\rho(D_{+\mu_{1},j}^{(0)})\leq
n^{3/2}.$ (A.78)

Denote

$\sigma_{+\mu_{1}}^{2}=\text{Var}\big{(}ma_{j}\phi(a_{j}D_{+\mu_{1},j}^{(0)})\big{)};\quad\rho_{+\mu_{1}}=\rho(ma_{j}\phi(a_{j}D_{+\mu_{1},j}^{(0)})).$

Combining (A.78) and results in Lemma A.14, we have

${\mathbb{E}}[ma_{j}\phi(a_{j}D_{+\mu_{1},j}^{(0)})]=\frac{e_{+\mu_{1}}}{2};\quad\max\\{\frac{n}{48},\frac{e_{+\mu_{1}}^{2}}{4}\\}\leq\sigma_{+\mu_{1}}^{2}\leq\max\\{\frac{n}{2},\frac{e_{+\mu_{1}}^{2}}{2}\\};\quad\rho_{+\mu_{1}}\leq
32\max\\{n^{3/2},|e_{+\mu_{1}}|^{3}\\}.$ (A.79)

Applying Berry-Esseen theorem, we have

${\mathbb{P}}(\Big{|}\sum_{j=1}^{m}a_{j}\phi(a_{j}D_{+\mu_{1},j}^{(0)})-\frac{1}{2}e_{+\mu_{1}}\Big{|}>t)\leq
2\bar{\Phi}\big{(}\frac{t\sqrt{m}}{\sigma_{+\mu_{1}}}\big{)}+\frac{C_{\text{BE}}\rho_{+\mu_{1}}}{\sigma_{+\mu_{1}}^{3}\sqrt{m}}\leq
2\bar{\Phi}\big{(}\frac{t\sqrt{m}}{\sqrt{n}+2C_{n}\sqrt{n\varepsilon}}\big{)}+\frac{C}{\sqrt{m}}$

for some universal constant $C>0$. Here the second inequality uses
$\sigma_{+\mu_{1}}^{2}\leq(\sqrt{n}+|e_{+\mu_{1}}|)^{2}$, which comes from
(A.79), and the last inequality uses (A.77). By the symmetry of $a_{j}$, we
have

${\mathbb{E}}[ma_{j}|a_{j}D_{+\mu_{1},j}^{(0)}|]=0;\quad\text{Var}(ma_{j}|a_{j}D_{+\mu_{1},j}^{(0)}|)={\mathbb{E}}[(D_{+\mu_{1},j}^{(0)})^{2}];\quad\rho(ma_{j}|a_{j}D_{+\mu_{1},j}^{(0)}|)={\mathbb{E}}[|D_{+\mu_{1},j}^{(0)}|^{3}].$

By (A.78), we have

$\frac{n}{24}+e_{+\mu_{1}}^{2}\leq{\mathbb{E}}[(D_{+\mu_{1},j}^{(0)})^{2}]\leq\frac{n}{2}+e_{+\mu_{1}}^{2};\quad{\mathbb{E}}[|D_{+\mu_{1},j}^{(0)}|^{3}]\leq
8(\rho(D_{+\mu_{1},j}^{(0)})+|e_{+\mu_{1}}|^{3})\leq
8(n^{3/2}+|e_{+\mu_{1}}|^{3}).$ (A.80)

Similarly, applying Berry-Esseen theorem, we have

${\mathbb{P}}(\Big{|}\sum_{j=1}^{m}a_{j}|a_{j}D_{+\mu_{1},j}^{(0)}|\Big{|}>t)\leq
2\bar{\Phi}\big{(}\frac{t\sqrt{m}}{\sqrt{n}+2C_{n}\sqrt{n\varepsilon}}\big{)}+\frac{C}{\sqrt{m}},$

where the inequality uses
$\text{Var}(ma_{j}|a_{j}D_{+\mu_{1},j}^{(0)}|)\leq(\sqrt{n}+|e_{+\mu_{1}}|)^{2}$
and (A.77). Then the results of this lemma are proved by noting that
$C_{n}\sqrt{\varepsilon}\geq 1$ for large enough $n$. ∎

######  Theorem A.13.

Suppose that Assumptions (A1)-(A6) hold. With probability at least
$1-O(1/\sqrt{m})-O(n^{-\varepsilon})$ over the initialization of the weights
and the generation of training data, after one iteration, the classifier
$\operatorname{sgn}(f(x,W^{(1)}))$ exhibits a generalization risk with the
following bounds:

$\tfrac{1}{2}(1-n^{-\varepsilon})\leq{\mathbb{P}}_{(x,y)\sim
P_{\text{clean}}}(y\neq\operatorname{sgn}(f(x;W^{(1)})))\leq\tfrac{1}{2}(1+n^{-\varepsilon}).$

###### Proof.

For any given training data $X\in\mathcal{G}_{\text{data}}$, denote the
expectation of $D_{\nu,j}^{(0)}$ by $e_{\nu}$, i.e.

$e_{\nu}:={\mathbb{E}}[D_{\nu,j}^{(0)}|X]=(c_{\nu}-n_{\nu}-c_{-\nu}+n_{-\nu})/2,\quad\nu\in\\{\pm\mu_{1},\pm\mu_{2}\\},$
(A.81)

and a set of parameters $\mathcal{G}_{X}$:

$\begin{split}\mathcal{G}_{X}:=\big{\\{}(a,W^{(0)}):&|\sum_{j=1}^{m}a_{j}\phi(a_{j}D_{\nu,j}^{(0)})-e_{\nu}/2|\leq
3C_{n}\sqrt{n\varepsilon/m}\log(m),\\\
&\big{|}\sum_{j=1}^{m}a_{j}|a_{j}D_{\nu,j}^{(0)}|\big{|}\leq
3C_{n}\sqrt{n\varepsilon/m}\log(m),a\in\mathcal{G}_{A},W^{(0)}\in\mathcal{G}_{W}\big{\\}}.\end{split}$

Applying the union bound, we have

${\mathbb{P}}(\mathcal{G}_{X}|X\in\mathcal{G}_{\text{data}})\geq
1-\exp(-\Omega(\log^{2}(m)))-\frac{2C}{\sqrt{m}}-n^{-\varepsilon}$

by Lemma A.12 and 4.3. Further we have

$\begin{split}{\mathbb{P}}((a,W^{(0)})\in\mathcal{G}_{X},X\in\mathcal{G}_{\text{data}})&\geq{\mathbb{P}}(\mathcal{G}_{X}|X\in\mathcal{G}_{\text{data}}){\mathbb{P}}(X\in\mathcal{G}_{\text{data}})\\\
&\geq 1-\exp(-\log^{2}(m)/2)-\frac{2C}{\sqrt{m}}-2n^{-\varepsilon}\\\ &\geq
1-\frac{3C}{\sqrt{m}}-2n^{-\varepsilon}.\end{split}$

Define events $\mathcal{F}_{{\text{test}},\nu}$ for test data:

$\begin{split}\mathcal{F}_{{\text{test}},\nu}=\\{x\in\mathbb{R}^{p}:&|\|x\|^{2}-p-\|\mu\|^{2}|\leq
10\sqrt{p\log(n)};\\\ &|\langle
x,x_{i}\rangle-\langle\nu,\bar{x}_{i}\rangle|\leq 10\sqrt{p\log(n)}\text{ for
all }i\in[n]\\},\quad\nu\in\\{\pm\mu_{1},\pm\mu_{2}\\}.\end{split}$

Treat $\\{x\\}\cup\\{x_{i}\\}_{i=1}^{n}$ as a new ‘training’ set with $n+1$
datapoints. Following the proof procedure in Lemma 4.1, we can show that
${\mathbb{P}}_{x\sim
N(\nu,I_{p})}(x\in\mathcal{F}_{{\text{test}}}|X\in\mathcal{G}_{{\text{data}}})\geq
1-n^{-\varepsilon}$, where
$\mathcal{F}_{{\text{test}}}:=\cup_{\nu\in\\{\pm\mu_{1},\pm\mu_{2}\\}}\mathcal{F}_{{\text{test}},\nu}$.
And $\mathcal{F}_{{\text{test}}}$ is a symmetric set for $x$, i.e., if
$x\in\mathcal{F}_{{\text{test}}}$, then $-x$ also belongs to
$\mathcal{F}_{{\text{test}}}$. In the remaining proof, by convention all
probabilities and expectations are implicitly conditioned on fixed
$X\in\mathcal{G}_{\text{data}}$ and $a,W^{(0)}\in\mathcal{G}_{X}$. Therefore,
to simplify notation, we write ${\mathbb{P}}(\,\cdot\,)$ and
${\mathbb{E}}[\,\cdot\,]$ to denote
${\mathbb{P}}(\,\cdot\,|a,W^{(0)},\\{x_{i}\\})$ and
${\mathbb{E}}[\,\cdot\,|a,W^{(0)},\\{x_{i}\\}]$, respectively. In other words,
the randomness is over the test data $(x,y)$, conditioned on a fixed
initialization and training data. We first look at the clusters centered at
$\pm\mu_{1}$, i.e. $x\sim N(\pm\mu_{1},I_{p}),y=1$. Then we have

$\begin{split}{\mathbb{P}}&{}_{x\sim
N(\pm\mu_{1},I_{p})}(y\neq\operatorname{sgn}(f(x,W^{(1)})))={\mathbb{P}}_{x\sim
N(\pm\mu_{1},I_{p})}(f(x,W^{(1)})\leq 0)\\\ &=\frac{1}{2}{\mathbb{P}}_{x\sim
N(\mu_{1},I_{p})}(f(x,W^{(1)})\leq 0)+\frac{1}{2}{\mathbb{P}}_{x\sim
N(\mu_{1},I_{p})}(f(-x,W^{(1)})\leq 0).\end{split}$ (A.82)

Note that given $W^{(0)}$ and $X$, we have with probability $1$ that

$\begin{split}|f(x;W^{(1)})-f(x;W^{(1)}-W^{(0)})|&=\Big{|}\sum_{j=1}^{m}a_{j}[\phi(\langle
w_{j}^{(1)},x\rangle)-\phi(\langle
w_{j}^{(1)}-w_{j}^{(0)},x\rangle)]\Big{|}\\\ &\leq\sum_{j=1}^{m}|a_{j}\langle
w_{j}^{(0)},x\rangle|\leq\sqrt{\sum_{j=1}^{m}a_{j}^{2}\sum_{j=1}^{m}\|w_{j}^{(0)}\|^{2}\cdot\|x\|^{2}}\\\
&=\|W^{(0)}\|_{F}\cdot\|x\|\leq\omega_{\text{init}}\sqrt{3mp/2}\|x\|,\end{split}$
(A.83)

where the first inequality comes from the $1$-Lipschitz continuity of
$\phi(\cdot)$; the second inequality uses Cauchy-Schwarz inequality; and the
last inequality uses Lemma 4.3. Next, recall that $W_{{\mathtt{T}}}$ is
defined as in (A.72). By the same argument above, we have

$\displaystyle|f(x;W^{(1)}-W^{(0)})-f(x;W_{{\mathtt{T}}}^{(1)}-W^{(0)})|$
$\displaystyle=\Big{|}\sum_{j=1}^{m}a_{j}[\phi(\langle
w_{j}^{(1)}-w_{j}^{(0)},x\rangle)-\phi(\langle
w_{j,{\mathtt{T}}}^{(1)}-w_{j}^{(0)},x\rangle)]\Big{|}$
$\displaystyle\leq\sum_{j=1}^{m}|a_{j}\langle
w_{j}^{(1)}-w_{j,{\mathtt{T}}}^{(1)},x\rangle|\leq\sqrt{\sum_{j=1}^{m}a_{j}^{2}\sum_{j=1}^{m}\|w_{j}^{(1)}-w_{j,{\mathtt{T}}}^{(1)}\|^{2}\cdot\|x\|^{2}}=\|W^{(1)}-W_{{\mathtt{T}}}^{(1)}\|_{F}\cdot\|x\|$
$\displaystyle\leq\alpha\omega_{\text{init}}p\sqrt{3mp/n}\|x\|\leq\omega_{\text{init}}\sqrt{3mp/n}\|x\|,$
(A.84)

where the first inequality comes from the $1$-Lipschitz continuity of
$\phi(\cdot)$; the second inequality uses Cauchy-Schwarz inequality; the third
inequality uses Lemma A.10; and the last inequality uses Assumption (A3).
Using (A.83) and (A.84), we have by the triangle inequality that

$|f(x;W^{(1)})-f(x;W_{{\mathtt{T}}}^{(1)}-W^{(0)})|\leq
2\omega_{\text{init}}\sqrt{mp}\|x\|=:\epsilon_{x},\quad\mbox{ that for any
$x\in\mathbb{R}^{p}$. }$ (A.85)

Recall that

$\langle w_{j,{\mathtt{T}}}^{(1)}-w_{j}^{(0)},x\rangle=\frac{\alpha
a_{j}}{2n}\sum_{i=1}^{n}\phi^{\prime}(\langle w_{j}^{(0)},x_{i}\rangle)\langle
y_{i}x_{i},x\rangle.$

Then under a good run, for $x\in\mathcal{F}_{{\text{test}}}$, we have that
with probability $1$,

$\Big{|}\langle w_{j,{\mathtt{T}}}^{(1)}-w_{j}^{(0)},x\rangle-\frac{\alpha
a_{j}}{2n}D_{+\mu_{1},j}^{(0)}\|\mu\|^{2}\Big{|}\leq\frac{\alpha}{\sqrt{m}}C_{n}\sqrt{p},$

where $C_{n}=10\sqrt{\log(n)}$ and the inequality uses the definition of
$\mathcal{F}_{{\text{test}}}$. It yields that

$\Big{|}f(x;W_{{\mathtt{T}}}^{(1)}-W^{(0)})-\sum_{j=1}^{m}\frac{\alpha
a_{j}}{2n}\phi(a_{j}D_{+\mu_{1},j}^{(0)})\|\mu\|^{2}\Big{|}\leq\alpha
C_{n}\sqrt{p}.$ (A.86)

According to the definition of $\mathcal{G}_{X}$, we have

$\Big{|}\sum_{j=1}^{m}\frac{\alpha
a_{j}}{2n}\phi(a_{j}D_{+\mu_{1},j}^{(0)})\|\mu\|^{2}-\frac{\alpha\|\mu\|^{2}}{4n}e_{+\mu_{1}}\Big{|}\leq\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}.$ (A.87)

Combining (A.85)-(A.87), we have

$\Big{|}f(x;W^{(1)})-\frac{\alpha\|\mu\|^{2}}{4n}e_{+\mu_{1}}\Big{|}\leq\epsilon_{x}+\alpha
C_{n}\sqrt{p}+\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}.$ (A.88)

The above inequality immediately implies that

${\mathbb{P}}(f(x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})\geq{\mathbb{P}}(\frac{\alpha\|\mu\|^{2}}{2n}e_{+\mu_{1}}\leq-\epsilon_{x}-\alpha
C_{n}\sqrt{p}-\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}|\mathcal{F}_{{\text{test}}}).$
(A.89)

Similar to (A.88), for $-x\sim N(-\mu_{1},I_{p})$, we have

$\Big{|}f(-x;W^{(1)})-\frac{\alpha\|\mu\|^{2}}{2n}e_{-\mu_{1}}\Big{|}\leq\epsilon_{x}+\alpha
C_{n}\sqrt{p}+\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}.$

Note that by definition, $e_{-\mu_{1}}=-e_{+\mu_{1}}$, the above inequality
immediately implies that

${\mathbb{P}}(f(-x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})\geq{\mathbb{P}}(\frac{\alpha\|\mu\|^{2}}{2n}e_{+\mu_{1}}\geq\epsilon_{x}+\alpha
C_{n}\sqrt{p}+\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}|\mathcal{F}_{{\text{test}}}).$
(A.90)

According to the definition of $\mathcal{G}_{{\text{test}}}$, we have
$\epsilon_{x}\leq 4\omega_{\text{init}}\sqrt{m}p^{3/2}$. According to the
definition of $\mathcal{G}_{{\text{data}}}$, we have

$\begin{split}|c_{\nu}-n_{\nu}-c_{-\nu}+n_{-\nu}|&\geq|c_{\nu}-c_{-\nu}|-|n_{\nu}-n_{-\nu}|\geq|c_{\nu}+n_{\nu}-c_{-\nu}-n_{-\nu}|-2|n_{\nu}-n_{-\nu}|\\\
&\geq(1-2\eta)n^{1/2-\varepsilon}\geq n^{1/2-\varepsilon}/2.\end{split}$

Thus we have $|e_{+\mu_{1}}|\geq n^{1/2-\varepsilon}/4$. It yields that

$\begin{split}&\frac{\alpha\|\mu\|^{2}}{2n}|e_{+\mu_{1}}|-\epsilon_{x}-\alpha
C_{n}\sqrt{p}-\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}\\\
&\geq\frac{\alpha\|\mu\|^{2}}{\sqrt{n}}\Big{(}\frac{1}{8n^{\varepsilon}}-4\sqrt{mn}p^{3/2}\frac{\omega_{\text{init}}}{\alpha\|\mu\|^{2}}-C_{n}\sqrt{\frac{np}{\|\mu\|^{4}}}-\frac{3C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{m}}\Big{)}\\\
&\geq\frac{\alpha\|\mu\|^{2}}{\sqrt{n}}\Big{(}\frac{1}{8n^{\varepsilon}}-\frac{2}{m\sqrt{n}}-\frac{C_{n}}{3Cn^{0.01}}-\frac{3C_{n}}{2\sqrt{C}n^{0.01}}\Big{)}>0,\end{split}$
(A.91)

where the first inequality uses $|e_{+\mu_{1}}|\geq n^{1/2-\varepsilon}/4$ and
$\epsilon_{x}\leq 4\omega_{\text{init}}\sqrt{m}p^{3/2}$; the second inequality
uses Assumption (A5), (A1) and (A6); and the last inequality uses $n$ is large
enough. Combining (A.89)-(A.91), we have

$\begin{split}&{\mathbb{P}}(f(x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})+{\mathbb{P}}(f(-x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})\\\
\geq&{\mathbb{P}}(\frac{\alpha\|\mu\|^{2}}{2n}|e_{+\mu_{1}}|\geq\epsilon_{x}+\alpha
C_{n}\sqrt{p}+\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}|\mathcal{F}_{{\text{test}}})=1,\end{split}$
(A.92)

where the inequality uses $\epsilon_{x}\geq 0$. Following a similar procedure,
for the other side, we have

$\begin{split}&{\mathbb{P}}(f(x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})+{\mathbb{P}}(f(-x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})\\\
\leq&{\mathbb{P}}(\frac{\alpha\|\mu\|^{2}}{2n}|e_{+\mu_{1}}|\geq-\epsilon_{x}-\alpha
C_{n}\sqrt{p}-\frac{3\alpha
C_{n}\sqrt{\varepsilon}\log(m)}{2\sqrt{mn}}\|\mu\|^{2}|\mathcal{F}_{{\text{test}}})=1.\end{split}$
(A.93)

Combining (A.92) and (A.93), we have

${\mathbb{P}}(f(x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})+{\mathbb{P}}(f(-x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})=1.$

Following the same procedure, we have that for any
$\nu\in\\{\pm\mu_{1},\pm\mu_{2}\\}$,

${\mathbb{P}}_{x\sim N(\nu,I_{p})}(yf(x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}})+{\mathbb{P}}_{x\sim
N(\nu,I_{p})}(yf(-x;W^{(1)})\leq 0|\mathcal{F}_{{\text{test}}})=1.$

Then for $(x,y)\sim P_{\text{clean}}$, we have

${\mathbb{P}}_{(x,y)\sim P_{\text{clean}}}(yf(x;W^{(1)})\leq
0)\geq{\mathbb{P}}(yf(x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}}){\mathbb{P}}(\mathcal{F}_{{\text{test}}})\geq\frac{1}{2}(1-n^{-\varepsilon});$
${\mathbb{P}}_{(x,y)\sim P_{\text{clean}}}(yf(x;W^{(1)})\leq
0)\leq{\mathbb{P}}(yf(x;W^{(1)})\leq
0|\mathcal{F}_{{\text{test}}}){\mathbb{P}}(\mathcal{F}_{{\text{test}}})+{\mathbb{P}}(\mathcal{F}_{{\text{test}}}^{c})\leq\frac{1}{2}(1+n^{-\varepsilon}).$

∎

###  A.6 Probability Lemmas

######  Lemma A.14.

Suppose we have a random variable $g$ that has finite $L_{3}$ norm and a
Rademacher variable $a$ that is independent with $g$. Then we have

$\max\\{\frac{1}{2}\text{Var}(g),\frac{1}{4}({\mathbb{E}}[g])^{2}\\}\leq\text{Var}(a\phi(ag))\leq\max\\{\text{Var}(g),\frac{1}{2}({\mathbb{E}}[g])^{2}\\};$
(A.94)
${\mathbb{E}}\big{[}\big{|}a\phi(ag)-{\mathbb{E}}[a\phi(ag))]\big{|}^{3}\big{]}\leq
32\max\\{{\mathbb{E}}[|g-{\mathbb{E}}[g]|^{3}],|{\mathbb{E}}[g]|^{3}\\}.$
(A.95)

###### Proof.

The expectation of the random variable $a\phi(ag)$ is

${\mathbb{E}}[a\phi(ag)]=\frac{1}{2}{\mathbb{E}}[\phi(g)-\phi(-g)]=\frac{1}{2}{\mathbb{E}}[g],$
(A.96)

where the first equation uses the law of expectation, and the second equation
uses $\phi(x)-\phi(-x)=x.$ The second moment of $a\phi(ag)$ is

${\mathbb{E}}[(a\phi(ag))^{2}]={\mathbb{E}}[\phi(ag)^{2}]=\frac{1}{2}{\mathbb{E}}[\phi(g)^{2}+\phi(-g)^{2}]=\frac{1}{2}{\mathbb{E}}[g^{2}],$
(A.97)

where the last equation uses $\phi(x)^{2}+\phi(-x)^{2}=x^{2}.$ Combining
(A.96) and (A.97), we have

$\text{Var}(a\phi(ag))=\frac{1}{2}{\mathbb{E}}[g^{2}]-\frac{1}{4}({\mathbb{E}}[g])^{2}=\frac{1}{2}\text{Var}(g)+\frac{1}{4}({\mathbb{E}}[g])^{2},$

which implies (A.94). Moreover, for a random variable $X$ that has finite
$L_{3}$ norm, we have

$\|X-{\mathbb{E}}[X]\|_{3}\leq\|X\|_{3}+\|{\mathbb{E}}[X]\|_{3}\leq\|X\|_{3}+{\mathbb{E}}[|X|]\leq
2\|X\|_{3},$

where the second inequality is due to
$\|{\mathbb{E}}[X]\|_{3}=|{\mathbb{E}}[X]|$ and the last inequality is due to
$\|X\|_{1}\leq\|X\|_{3}$. Thus we have

${\mathbb{E}}\big{[}\big{|}a\phi(ag)-\frac{1}{2}{\mathbb{E}}[g]\big{|}^{3}\big{]}\leq
8{\mathbb{E}}[|a\phi(ag)|^{3}]=4{\mathbb{E}}[\phi(g)^{3}+\phi(-g)^{3}]=4{\mathbb{E}}[|g|^{3}],$

where the last equation is due to $\phi(x)^{3}+\phi(-x)^{3}=|x|^{3}.$ Then by
$\|g\|_{3}\leq\|g-{\mathbb{E}}[g]\|_{3}+|{\mathbb{E}}[g]|$, we have

${\mathbb{E}}\big{[}\big{|}a\phi(ag)-\frac{1}{2}{\mathbb{E}}[g]\big{|}^{3}\big{]}\leq
4\big{(}\|g-{\mathbb{E}}[g]\|_{3}+|{\mathbb{E}}[g]|\big{)}^{3}\leq
32\max\\{{\mathbb{E}}[|g-{\mathbb{E}}[g]|^{3}],|{\mathbb{E}}[g]|^{3}\\}.$

∎

######  Lemma A.15.

Suppose $Z=[z_{1},\cdots,z_{n}]^{\top}\sim N(0,\Sigma)$, where
$\Sigma_{ii}=1,\text{ and }|\Sigma_{ij}|\leq 1/(Cn^{2}),1\leq i\neq j\leq n.$
And $Z^{\prime}=[z_{1}^{\prime},\cdots,z_{n}^{\prime}]^{\top}\sim
N(0,\mathbb{I}_{n})$. Let $b_{i}=\mathbb{I}(z_{i}>0)\text{ and
}b_{i}^{\prime}=\mathbb{I}(z_{i}^{\prime}>0),i\in[n]$ be Bernoulli random
variables. Let $B=[b_{1},\cdots,b_{n}]^{\top}$ and
$B^{\prime}=[b_{1}^{\prime},\cdots,b_{n}^{\prime}]^{\top}$. Then we have that
for any non-negative function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$,

$\frac{1}{2}{\mathbb{E}}_{B^{\prime}}[f(b_{1}^{\prime},\cdots,b_{n}^{\prime})]\leq{\mathbb{E}}_{B}[f(b_{1},\cdots,b_{n})]\leq
2{\mathbb{E}}_{B^{\prime}}[f(b_{1}^{\prime},\cdots,b_{n}^{\prime})].$

###### Proof.

Note that for any fixed value $(b_{1},\cdots,b_{n})\in\\{0,1\\}^{n}$,
${\mathbb{P}}_{B^{\prime}}(b_{1}^{\prime},\cdots,b_{n}^{\prime})=(1/2)^{n}$.
Then we have

$\begin{split}{\mathbb{E}}_{B}[f(b_{1},\cdots,b_{n})]&=\sum_{b_{1},\cdots,b_{n}}f(b_{1},\cdots,b_{n}){\mathbb{P}}_{B}(b_{1},\cdots,b_{n})\\\
&\geq(2\gamma_{1})^{n}\sum_{b_{1},\cdots,b_{n}}f(b_{1},\cdots,b_{n}){\mathbb{P}}_{B^{\prime}}(b_{1},\cdots,b_{n})\\\
&=(2\gamma_{1})^{n}{\mathbb{E}}_{B^{\prime}}[f(b_{1},\cdots,b_{n})],\end{split}$
(A.98)

where the inequality comes from Lemma A.16. On the other side, similarly we
have

${\mathbb{E}}_{B}[f(b_{1},\cdots,b_{n})]\leq(2\gamma_{2})^{n}{\mathbb{E}}_{B^{\prime}}[f(b_{1},\cdots,b_{n})].$
(A.99)

By $C>8$, we have $(2\gamma_{1})^{n}=(1-4/(Cn))^{n}\geq 1-4/(Cn)\geq 1/2$ and
$(2\gamma_{2})^{n}=(1+4/(Cn))^{n}\leq\exp(4/C)\leq\exp(1/2)\leq 2$. Combining
these results with (A.98) and (A.99), we have

$\frac{1}{2}{\mathbb{E}}_{B^{\prime}}[f(b_{1}^{\prime},\cdots,b_{n}^{\prime})]\leq{\mathbb{E}}_{B}[f(b_{1},\cdots,b_{n})]\leq
2{\mathbb{E}}_{B^{\prime}}[f(b_{1}^{\prime},\cdots,b_{n}^{\prime})].$

∎

######  Lemma A.16.

Suppose $Z=[z_{1},\cdots,z_{n}]^{\top}\sim N(0,\Sigma)$, where
$\Sigma_{ii}=1,\text{ and }|\Sigma_{ij}|\leq 1/(Cn^{2}),1\leq i\neq j\leq n.$
Then we have that for any subset ${\mathcal{A}}\subseteq[n]$,

$\gamma_{1}^{n}\leq{\mathbb{E}}[\prod_{i\in{\mathcal{A}}}\mathbb{I}(z_{i}>0)\cdot\prod_{i\in[n]\backslash{\mathcal{A}}}\mathbb{I}(z_{i}<0)]\leq\gamma_{2}^{n}$

for $\gamma_{1}=1/2-2/(Cn)$ and $\gamma_{2}=1/2+2/(Cn)$.

###### Proof.

We first prove the result for ${\mathcal{A}}=[n]$. Note that

${\mathbb{P}}(z_{1}>0,\cdots,z_{n}>0)={\mathbb{P}}(z_{1}>0)\prod_{k=2}^{n}{\mathbb{P}}(z_{k}>0|z_{k-1}>0,\cdots,z_{1}>0).$
(A.100)

Let $Z_{k-1}=[z_{1},\cdots,z_{k-1}]^{\top}$ and denote the covariance matrix
of $[z_{1},\cdots,z_{k}]$ as

$\begin{split}\left[\begin{array}[]{cc}\Sigma_{k-1}&\epsilon_{k}\\\
\epsilon_{k}^{\top}&1\end{array}\right],\end{split}$

where $\Sigma_{k-1}=\text{Cov}(Z_{k-1})$ and
$\epsilon_{k}=\text{Cov}(Z_{k-1},z_{k})$. Then $|\epsilon_{kj}|\leq
1/(Cn^{2})$ for $j\in[k-1]$, and the conditional distribution of
$z_{k}|Z_{k-1}$ is
$N(\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}Z_{k-1},1-\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}\epsilon_{k})$.
By Gershgorin circle theorem, we have

$1-\frac{1}{Cn}\leq\lambda_{\min}(\Sigma_{k-1})\leq\lambda_{\max}(\Sigma_{k-1})\leq
1+\frac{1}{Cn}.$

Denote $f_{k-1}(\cdot)$ as the density function of $Z_{k-1}$. Then we have

$\begin{split}{\mathbb{P}}(z_{k}>0|z_{k-1}>0,\cdots,z_{1}>0)&=\int_{0}^{\infty}\cdots\int_{0}^{\infty}f_{k-1}(Z_{k-1})\bar{\Phi}\Big{(}\frac{-\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}Z_{k-1}}{\sqrt{1-\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}\epsilon_{k}}}\Big{)}dz_{1}\cdots
dz_{k-1}\\\ &\geq\int_{\|\Sigma_{k-1}^{-1/2}Z_{k-1}\|\leq
2\sqrt{n}}f_{k-1}(Z_{k-1})\bar{\Phi}\Big{(}\frac{-\epsilon_{k}\Sigma_{k-1}^{-1}Z_{k-1}}{\sqrt{1-\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}\epsilon_{k}}}\Big{)}dz_{1}\cdots
dz_{k-1}\\\
&\geq\Big{(}\frac{1}{2}-\frac{\|\Sigma_{k-1}^{-1/2}\epsilon_{k}\|\cdot
2\sqrt{n}}{\sqrt{2\pi(1-\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}\epsilon_{k})}}\Big{)}{\mathbb{P}}(\|\Sigma_{k-1}^{-1/2}Z_{k-1}\|\leq
2\sqrt{n})\\\
&\geq\big{(}\frac{1}{2}-\frac{2\sqrt{2}}{nC\sqrt{\pi}}\big{)}{\mathbb{P}}(\|\Sigma_{k-1}^{-1/2}Z_{k-1}\|\leq
2\sqrt{n})\\\
&\geq\big{(}\frac{1}{2}-\frac{2\sqrt{2}}{nC\sqrt{\pi}}\big{)}(1-\exp(-n))\geq\frac{1}{2}-\frac{2}{Cn}\end{split}$
(A.101)

for sufficiently large $n$. Here the second inequality uses
$|\Phi(x)-\Phi(0)|\leq\Phi^{\prime}(0)|x|$ and Cauchy-Schwarz inequality; the
third inequality uses
$\sigma_{\min}(\Sigma_{k-1})=\lambda_{\min}(\Sigma_{k-1})\geq 1/2$ and
$\|\Sigma_{k-1}^{-1/2}\epsilon_{k}\|\leq\sqrt{2}\|\epsilon_{k}\|\leq\sqrt{2}n^{-3/2}/C$;
and the fourth inequality uses the concentration inequality for chi-square
random variables in Lemma A.17. Then the result is proved by combining (A.100)
and (A.101). On the other side, we have

$\begin{split}{\mathbb{P}}(z_{k}>0|z_{k-1}>0,\cdots,z_{1}>0)&\leq\int_{\|\Sigma_{k-1}^{-1/2}Z_{k-1}\|\leq
2\sqrt{n}}f_{k-1}(Z_{k-1})\bar{\Phi}\Big{(}\frac{-\epsilon_{k}\Sigma_{k-1}^{-1}Z_{k-1}}{\sqrt{1-\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}\epsilon_{k}}}\Big{)}dz_{1}\cdots
dz_{k-1}\\\ &+{\mathbb{P}}(\|\Sigma_{k-1}^{-1/2}Z_{k-1}\|>2\sqrt{n})\\\
&\leq\Big{(}\frac{1}{2}+\frac{\|\Sigma_{k-1}^{-1/2}\epsilon_{k}\|\cdot
2\sqrt{n}}{\sqrt{2\pi(1-\epsilon_{k}^{\top}\Sigma_{k-1}^{-1}\epsilon_{k})}}\Big{)}+{\mathbb{P}}(\|\Sigma_{k-1}^{-1/2}Z_{k-1}\|>2\sqrt{n})\\\
&\leq\frac{1}{2}+\frac{2\sqrt{2}}{nC\sqrt{\pi}}+\exp(-n)\leq\frac{1}{2}+\frac{2}{Cn}.\end{split}$

Note that our proof does not use any information related to ${\mathcal{A}}$,
thus we can extend the result for any subset ${\mathcal{A}}\subseteq[n]$. ∎

######  Lemma A.17.

For $X_{k}\text{ i.i.d}\sim N(0,\sigma^{2}),1\leq k\leq n$, we have

$\Phi^{\prime}(t)/t\leq{\mathbb{P}}(|X_{1}|\geq
t\sigma)\leq\exp(-t^{2}/2),\quad\forall t\geq 1;$
${\mathbb{P}}(\big{|}\frac{1}{n\sigma^{2}}\sum_{k=1}^{n}X_{k}^{2}-1\big{|}\geq
t)\leq 2\exp(-nt^{2}/8),\quad\forall t\in(0,1).$

###### Proof.

For the first inequality, we note that

$\bar{\Phi}(t)=\int_{t}^{+\infty}\frac{x}{\sqrt{2\pi}x}\exp(-\frac{1}{2}x^{2})dx\leq\int_{t}^{+\infty}\frac{1}{2\sqrt{2\pi}t}\exp(-\frac{1}{2}x^{2})dx^{2}=\frac{\Phi^{\prime}(t)}{t}.$

It yields that for any $t\geq 1$,

${\mathbb{P}}(|X_{1}|\geq t\sigma)=2\bar{\Phi}(t)\leq
2\Phi^{\prime}(t)/t\leq\exp(-t^{2}/2).$

On the other side, we have

$\bar{\Phi}(t)\geq\int_{t}^{+\infty}\frac{\frac{1+x^{2}}{x^{2}}}{\sqrt{2\pi}\frac{1+t^{2}}{t^{2}}}\exp(-\frac{1}{2}x^{2})dx=\frac{1}{\sqrt{2\pi}}\frac{t^{2}}{1+t^{2}}\Big{(}-\frac{\exp(-\frac{x^{2}}{2})}{x}\Big{)}\Big{|}_{x=t}^{+\infty}=\frac{t}{1+t^{2}}\Phi^{\prime}(t).$

When $t\geq 1$, it further yields that
$\bar{\Phi}(t)\geq\Phi^{\prime}(t)/(2t)$. Thus we have

${\mathbb{P}}(|X_{1}|\geq t\sigma)=2\bar{\Phi}(t)\geq\Phi^{\prime}(t)/t.$

The second inequality is Example 2.11 in [Wai19] ∎

######  Lemma A.18 (Hoeffding’s inequality, Equation (2.11) in [Wai19]).

Let $X_{k},1\leq k\leq n$ be a series of independent random variables with
$X_{k}\in[a,b]$. Then

${\mathbb{P}}(\sum_{k=1}^{n}(X_{k}-{\mathbb{E}}[X_{k}])\geq
t)\leq\exp\Big{(}-\frac{2t^{2}}{n(b-a)^{2}}\Big{)},\quad\forall t\geq 0.$

######  Lemma A.19.

[Berry-Esseen Theorem, Theorem 3.4.17 in [Dur19]] Let $X_{1},\cdots,X_{n}$ are
i.i.d. random variables with
${\mathbb{E}}[X_{i}]=0,\text{Var}(X_{i})=\sigma^{2}$, and
${\mathbb{E}}[|X_{i}|^{3}]=\rho<\infty$. If $F_{n}(x)$ is the distribution of
$\sum_{i=1}^{n}X_{i}/(\sigma\sqrt{n})$, then

$|F_{n}(x)-\Phi(x)|\leq\frac{3\rho}{\sigma^{3}\sqrt{n}}.$

###  A.7 Experimental details

In our experiments, dimension $p=40000$, number of train/test samples $n=200$
$\mu=2.5\sqrt{p/n}$, number of neurons $m=1000$, label noise rate $\eta=0.05$,
and initial weight scale $\omega_{\text{init }}=10^{-15}$. For Figure 3, 2,
and 1-left, the step size $\alpha=10^{-12}$. For Figure 4 and 1-right,
$\alpha=10^{-16}$.

Figure 4: Histograms of inner products between positive neurons and $\mu$’s
pooled over 100 independent runs under the same setting as in Figure 1 but
with a smaller step size. _Top (resp. bottom) row:_ Inner products between
positive neurons and $\mu_{1}$ (resp. $\mu_{2}$). While the projections of
positive neurons $w_{j}^{(t)}$ onto the $\mu_{1}$ and $\mu_{2}$ directions
have nearly the same distribution when the network cannot generalize, they
become much more aligned with $\pm\mu_{1}$ when the network can generalize.