# Evidence of cluster dipole states in germanium detectors operating at
temperatures below 10 K

D.-M. Mei  Corresponding author.
Email<EMAIL_ADDRESS>Department of Physics, The University of South
Dakota, Vermillion, SD 57069, USA  R. Panth  Department of Physics, The
University of South Dakota, Vermillion, SD 57069, USA  K. Kooi  Department of
Physics, The University of South Dakota, Vermillion, SD 57069, USA  H. Mei
Department of Physics, The University of South Dakota, Vermillion, SD 57069,
USA  S. Bhattarai  Department of Physics, The University of South Dakota,
Vermillion, SD 57069, USA  M. Raut  Department of Physics, The University of
South Dakota, Vermillion, SD 57069, USA  P. Acharya  Department of Physics,
The University of South Dakota, Vermillion, SD 57069, USA  G.-J. Wang
Department of Physics, The University of South Dakota, Vermillion, SD 57069,
USA

(August 28, 2024)

###### Abstract

By studying charge trapping in germanium (Ge) detectors operating at
temperatures below 10 K, we demonstrate for the first time that the formation
of cluster dipole states from residual impurities is responsible for charge
trapping. Two planar detectors with different impurity levels and types are
used in this study. When drifting the localized charge carriers created by
$\alpha$ particles from the top surface across a detector under a lower bias
voltage, significant charge trapping is observed when compared to operating at
a higher bias voltage. The amount of charge trapping shows a strong dependence
on the type of charge carriers. Electrons are trapped more than holes in a
p-type detector while holes are trapped more than electrons in a n-type
detector. When both electrons and holes are drifted simultaneously using the
widespread charge carriers created by $\gamma$ rays inside the detector, the
amount of charge trapping shows no dependence on the polarity of bias voltage.

Suggested keywords

††preprint: APS/123-QED

Low-background germanium (Ge) crystal detectors are a well-accepted technology
in the search for dark matter (DM) cogent ; cdms ; supercdms ; edelweiss ;
cdex  and neutrinoless double-beta (0$\nu\beta\beta$) decay hvkk ; igex ;
gerda ; majorana . The next generation of ton-scale experiments aims to
achieve: (a) an extremely low-energy threshold, below 100 eV of nuclear
recoils, to detect low-mass DM particles essig ; ahmed ; mei  and (b) an
extremely low-level background rate, 0.01 events/ton/year in the region of
interest (ROI) legend , for 0$\nu\beta\beta$ decay. This requires large-size
Ge crystals (2 to 4 kg) with sufficient purity for developing detectors with:
(i) internal charge or phonon amplification for DM mei ; ahmed  and (ii)
capable of differentiating a two-electron signature from 0$\nu\beta\beta$
decay and Compton scatters from background events legend . Both require the
charge trapping in Ge detectors to be well-understood in order to achieve best
energy resolution. While the charge trapping is relatively well-understood for
the detectors operating at temperatures around gerda ; majorana  77 K and
milli-Kelvin supercdms ; edelweiss , very little is understood for the charge
trapping in the detectors operating around the liquid helium temperature.

The residual impurities (donors or acceptors) in Ge freeze out from the
conduction or valence band to localized states, forming electric dipoles or
neutral states D0 and A0 around liquid helium temperature ($\sim$4 K) abak1 ;
abak2 ; gsad ; dven . As a result, the density of free charge carriers
decreases exponentially as temperature decreases nea ; str . When the
temperature approaches below 10 K, most of the donor (or acceptor) atoms
remain unionized. The fifth electrons (or the empty holes) are confined to the
donor (or the acceptor) atoms. The range of the confinement is determined by
the Onsager radius sager ; onsager ; ual ; mei1 ,
R=$\frac{1}{4\pi\epsilon\epsilon_{0}k_{B}T}$, where $\epsilon$ = 16.2 is the
relative permittivity for Ge, $\epsilon_{0}$ is the permittivity of free
space, $k_{B}$ is the Boltzmann constant, and $T$ is temperature. This Onsager
radius can be much larger than the size of donor or acceptor atom at
temperatures below 10 K. Consequently, the fifth electrons (or the empty
holes) tied to the donor (or acceptor) atoms can be thermally separated from
the cores of the atoms. This separation of positive and negative charges forms
an electric dipole. Since the orbital position of bound electrons or holes can
be thermally shifted away from their original orbits, the bound electrons or
holes are in the excited states. Therefore, the formed dipole states are
thermally excited, labelled as $D^{0^{*}}$ (or $A^{0^{*}}$), which is
different from the ground state of $D^{0}$ (or $A^{0}$).

Subsequently, the formed dipole states can trap charge through Coulomb
attraction to form cluster dipole states. Figure 1 depicts the formation of
excited dipole states and cluster dipole states in n-type Ge or p-type Ge,
respectively. The excited dipole states can be shallow traps or deep traps lax
; mei1 . Shallow traps form cluster dipole states where the charge can be
released through phonon excitation lax ; mei1 . While deep traps produce
single space-charged states because positive and negative charges are
recombined lax ; mei1  through capture. The probability of shallow traps is
much larger than that of deep traps according to the Lax model lax .

Figure 1: The sketch of the processes involved in the formation of the excited
dipole states and the cluster dipole states in an n-type (upper) and a p-type
(lower) Ge detector operated at temperatures below 10 K, where $\vec{p}$ and
$\vec{q}$ are the corresponding dipole moments.

Within an excited dipole state, the positively charged donor ion (or
negatively charged acceptor ion) is deeply confined by the lattice deformation
potential jba , the allowable phase space for trapping charge carriers is
smaller than that of bound electrons (or holes), which can move within the
range confined by the Onsager radius. Thus, it is expected that the
probability of forming $D^{+^{*}}$ states (or $A^{-^{*}}$ states) is larger
than that of $D^{-^{*}}$ states (or $A^{+^{*}}$ states) in an n-type detector
(or a p-type detector). This is to say that holes are trapped more severely
compared to electrons in an n-type detector and electrons are trapped more
than holes in a p-type detector. Note that although the trapping of charge
carriers by excited dipole states to form cluster dipole states has much in
common with binding of the carriers into excitons, the formation processes are
very different exciton .

We report here the results of the spectral analysis of charge trapping of
$D^{0^{*}}$ (or $A^{0^{*}}$) states in an n-type (or a p-type) Ge planar
detector operated at cryogenic temperature of 5.2 K. The measured energy
deposition of the 5.3 MeV $\alpha$ from an 241Am source is used as the
detecting mechanism. The analysis is compared to the same detector operated at
77.8 K. The charge trapping mechanism is demonstrated using the localized
charge carriers created by $\alpha$ particles from the top of the surface
across the detector under a lower bias voltage. The dependence of charge
trapping on the type of charge carriers (electrons vs holes) in a given
detector is shown when the detector is operated with different polarities of
bias voltage (positive vs negative). The widespread charge carriers created by
661.7 keV $\gamma$ rays from a 137Cs source are used to verify the trapping
mechanism.

Both n-type and p-type Ge crystals grown at the University of South Dakota
wang1 ; wang2 ; wang3  were fabricated into thin-contact planar detectors mang
; wei1 ; wei2 . A layer of amorphous Ge (a-Ge) with a thickness of $\sim$600
nm was coated on the Ge crystal surface as the electrical contact to block the
surface charges wei1 ; wei2 . On the surface of the a-Ge, a thin aluminum (Al)
layer ($\sim$100 nm) was deposited by using a sputtering machine to increase
conductivity. The detector is mounted into a cryostat and cooled down to about
5.2 K using a pulse tube refrigerator. Figure 2 shows the experimental setup.
There are two temperature sensors inside the detector house. One is mounted at
the bottom of a copper plate on which the detector is set on a thin indium
foil. The other one is set on the top of another copper plate, which is close
to the top surface of the detector. Thus, the detector is set between two
temperature sensors. Since the measured temperatures from the two sensors are
always different from each other by less than 0.5 K, this configuration
ensures the detector temperature is measured with an accuracy of 0.5 K.

Figure 2: Shown is the experimental setup for measuring energy deposition of
the 5.3 MeV $\alpha$ particles from a ${}^{241}Am$ source and the 661.7 keV
$\gamma$ rays from a 137Cs source. Left: a planar detector is mounted in the
cryostat; Middle: the detector is enclosed in the house with temperature
sensors; Right: the enclosed cryostat.

Two detectors, an n-type (R09-02) and a p-type (RL) with respective net
impurity densities of 7.02$\times$1010/cm3 and 6.2$\times$109/cm3, are cooled
down to 5.2 K. The dimensions of R09-02 are 11.7 mm $\times$ 11.5 mm $\times$
5.5 mm while RL has dimensions of 18.8 mm $\times$ 17.9 mm $\times$ 10.7 mm.
The relative capacitance of a given detector is measured at different
temperatures as shown in Figure 3. At zero bias, the relative capacitance
stays constant until the temperature reaches about 10 K. Below 10 K, the
relative capacitance decreases quickly to approach a constant level when the
temperature reaches 6.5 K. Below this temperature, the relative capacitance is
at the same level as the detector is fully depleted at 77.8 K. Similar
behavior was observed in other early measurements dven ; dve1 . This
demonstrates the detector is neutralized at a temperature below 6.5 K with
zero bias voltage. In this temperature region, the formation of excited dipole
states ensures the neutrality of the detector.

Figure 3: Shown is the relative capacitance versus temperature. The errors on
the relative capacitance is within 3% while the error of temperature is within
0.5 K.

The detector, R09-02 or RL, is biased according to a configuration with two
operation modes: Mode 1: a negative bias is applied to the bottom surface;
Mode 2: a positive bias is applied to the bottom surface. In both Mode 1 and
Mode 2, the top surface is grounded and the charge signal is collected through
the top contact. Using the localized charge carriers near the top surface
created by $\alpha$ particles from 241Am, this configuration allows the
electric field to drift one type of charge carriers across the detector at a
given bias voltage. When the detector is operated in Mode 1, holes are drifted
across the detector. While in Mode 2, electrons are drifted across the
detector. Therefore, the charge trapping can be studied for holes and
electrons separately for a given n-type or a p-type detector using $\alpha$
particles. For the widespread charge carriers created by the 661.7 keV
$\gamma$ rays, both holes and electrons are drifted across the detector.
Therefore, we expect to observe a symmetrical charge collection with respect
to the polarity of the bias voltage.

An 241Am source is mounted above the detector (see Figure 2.) inside the
cryostat. The source is taken from a smoke detector so that $\alpha$ particles
from the 241Am decays can arrive at the surface of the Ge detector. Since the
sum of the Al layer and the a-Ge layer is very thin ($\sim$ 700 nm), we
observe the $\alpha$ peak in the spectra from the detector and perform
different measurements over the course of two months.

Figure 4: The first two plots show the measured energy deposition from the 5.3
MeV $\alpha$s in an n-type detector, R09-02. #1: the detector was operated in
Mode 1. #2: the detector was operated in Mode 2. The second two plots show the
measured energy deposition from the 5.3 MeV $\alpha$s in a p-type detector,
RL. #3: the detector was operated in Mode 1. #4: the detector was operated in
Mode 2.

We use the data measured at various bias voltages to characterize the charge
trapping and to study how the charge trapping varies with bias voltage and the
polarity of bias voltage. The first two plots (#1 and #2) of Figure 4 present
the result of the 5.3 MeV $\alpha$ energy deposited in an n-type detector
operated at 5.2 K. Since the 241Am source is positioned above the top of the
detector, the localized holes produced on the surface are drifted through the
full detector thickness in Mode 1 with a negative bias voltage. As can be seen
from the first plot (#1) of Figure 4, the holes are significantly trapped when
the detector is operated at lower bias voltages and the peak of 5.3 MeV is not
even seen clearly until the bias voltage is increased to 1200 volts. The
relative charge collection efficiency ($\varepsilon_{h}$) at 1200 volts is
only $\sim$71% when compared to 1800 volts. If one uses
$\varepsilon_{h}=\frac{\lambda_{h}}{L}[1-exp(-L/\lambda_{h})]$ mei1  to
determine the trapping length for holes ($\lambda_{h}$) where $L$ = 5.5 mm is
the detector thickness, $\lambda_{h}$ = 0.75 cm. When the same detector is
operated in Mode 2 with a positive bias applied to the bottom of the detector,
electrons are drifted across the detector (#2 of Figure 4). The observation
indicates a strong charge trapping at 30 volts, a factor of $\sim$7 reduction
in charge collection, compared to 1800 volts. The charge collection efficiency
($\varepsilon_{e}$) at 1200 volts relative to 1800 volts is $\sim$99.9%, which
corresponds to a trapping length of 100 cm for electrons ($\lambda_{e}$) at
1200 volts. This observation suggests that electrons are less heavily trapped
($\lambda_{e}$ = 100 cm at 1200 volts) in an n-type detector when compared to
holes ($\lambda_{e}$ = 0.75 cm at 1200 volts). The holes trapped by
$D^{0^{*}}$ form $D^{+^{*}}$ states and the electrons trapped by $D^{0^{*}}$
form $D^{-^{*}}$ states in an n-type detector as demonstrated in Figure 1. The
observation shown in the first two plots (#1 and #2) of Figure 4 indicates the
probability of forming $D^{+^{*}}$ states is larger than that of $D^{-^{*}}$
states.

Similarly, the energy deposition in the detector RL (a p-type detector) from
the 5.3 MeV $\alpha$ particles is shown in the second two plots (#3 and #4) of
Figure 4. When the detector RL is operated in Mode 1 during which holes are
drifted across the detector, a significant charge trapping, a factor of
$\sim$7 reduction in charge collection at 30 volts compared to 1200 volts, is
observed (#3 of Figure 4) . The charge trapping is also observed when the bias
voltage is at 200 volts and 600 volts compared to 1200 volts. The charge
collection efficiency ($\varepsilon_{h}$) at 600 volts relative to 1200 volts
is $\sim$92%, which corresponds to a trapping length of 6.5 cm for holes
($\lambda_{h}$) at 600 volts when $L$ = 10.7 mm. When the polarity of bias
voltage is switched to Mode 2 during which electrons are drifted across the
detector (#4 of Figure 4), more severe charge trapping is observed at 200
volts and 600 volts when compared to the same voltages in Mode 1. For example,
the charge collection efficiency ($\varepsilon_{e}$) at 600 volts relative to
1200 volts is only $\sim$81.8%, which corresponds to a trapping length of 2.6
cm for electrons ($\lambda_{e}$). This indicates that electrons trapped more
severely ($\lambda_{e}$ = 2.6 cm at 600 volts) than holes ($\lambda_{h}$ = 6.5
cm at 600 volts) in a p-type detector. The electrons trapped by $A^{0^{*}}$
form $A^{-^{*}}$ states and the holes trapped by $A^{0^{*}}$ form $A^{+^{*}}$
states in a p-type detector as demonstrated in Figure 1. The observation shown
in the second two plots (#3 and #4 ) of Figure 4 suggests the probability of
forming $A^{-^{*}}$ states is larger than that of $A^{+^{*}}$ states.

The observation of more holes (electrons) trapped in an n-type (a p-type)
detector agrees with the prediction of the trapping mechanism: the Coulomb
attraction induced by the excited dipoles to form cluster dipole states. This
is because if the charge trapping were due to capture processes, one would
expect electrons (holes) to be trapped more than holes (electrons) in an
n-type (a p-type) detector since the same-side capture cross section
(electrons capture by donors or holes capture by acceptors) is three orders of
magnitude larger than the across band gap capture cross section (electron
capture by acceptors and holes capture by donors) phip1 ; phip ; sund ; sund1
.

As a cross check of the charge trapping mechanism, both detectors (R09-02 and
RL) are operated at 77.8 K at which the charge trapping is dominated by the
space charged-states (donor ion states and acceptor ion states) left from
depleting the detector. The first two plots (#1 and #2) of Figure 5 show the
normalized charge collection efficiency for the charge created by the 5.3 MeV
$\alpha$ particles versus the applied bias voltage at different temperatures
with Mode 1 and Mode 2. The normalization is performed for both detectors
operated at 77.8 K with 1800 volts for R09-02 detector and -1200 volts for RL
detector.

Figure 5: The first two plots (#1 and #2) show the normalized charge
collection for the charge created by the 5.3 MeV $\alpha$ particles versus the
applied bias voltage at different temperatures with Mode 1 and Mode 2. #1:
R09-02, an n-type detector. #2: RL, a p-type detector. The second two plots
(#3 and #4) show the normalized charge collection efficiency for the charge
created by the 661.7 keV $\gamma$ rays versus the applied bias voltage at
different temperatures with Mode 1 and Mode 2. #3: R09-02, an n-type detector.
#4: RL, a p-type detector.

At 77.8 K, the detector R09-02 is fully depleted at 1200 volts. When it is
operated at 1800 volts, charge trapping is minimized and the peak position of
$\alpha$ is determined to be $\sim$3.8 MeV, which implies an energy loss of
1.5 MeV due to continuous energy loss of $\alpha$ particles on the way from
the source to the detector. The energy scale of the detector is calibrated by
well known $\gamma$ rays. Similarly, the detector RL is fully depleted at 400
volts. When the detector is operated at 1200 volts, the peak position of
$\alpha$ is determined to be $\sim$3.3 MeV. The difference in energy loss of
$\alpha$ particles on the way from the source and the detector between R09-02
and RL is mainly due to the thickness of the a-Ge layer as the electrical
contacts for both detectors. The difference in the peak position of $\alpha$
at different bias voltages relative to the peak position at 77.8 K operated at
1800 volts for R09-02 and 1200 volts for RL demonstrates the amount of charge
trapping. At 77.8 K, charge trapping is dominated by the Coulomb attraction
between the space-charged states and the corresponding charge carriers. At 5.2
K, since the detector is neutralized in charge states, charge trapping is
mainly due to the Coulomb attraction between dipole states and the
corresponding charge carriers.

To further verify the charge trapping mechanism, both detectors are exposed to
the 661.7 keV $\gamma$ rays from a ${}^{137}Cs$ source. Both positive bias and
negative bias are applied to the bottom surface of both detectors. Since
widespread charge carriers inside the detector are expected from the 661.7 keV
$\gamma$ rays, the charge trapping is anticipated to have no dependence on the
polarity of bias voltage in both detectors. The second two plots (#3 and #4)
of Figure 5 show the normalized charge collection efficiency versus the
applied bias voltage for both detectors at different temperatures. As can be
seen, the amount of charge trapping between positive bias and negative bias in
both detectors is almost the same. The charge trapping has no dependence on
positive or negative bias voltages in both detectors. The correlation between
charge trapping and the impurity level is noticeable from the measurements of
the 661.7 keV $\gamma$ rays in R09-02 and RL detectors operated at 5.2 K. For
example, when both detectors are applied a bias of 300 volts, more charge
trapping (a factor of $\sim$1.6 reduction in charge collection) is observed in
R02-02 detector (#3 of Figure 5) compared to the charge trapping in RL (#4 of
Figure 5), which has a smaller net impurity concentration. It is worth
mentioning that significant charge trapping at 4.2 K was also reported by D.
Vénos et al. dven ; dve1  in p-type detectors operated at lower bias voltage.

We conclude that the observed charge trapping at 5.2 K is due to the Coulomb
attraction between excited dipole states and corresponding charge carriers. At
5.2 K, it is tempting to speculate that cluster dipole states are being formed
and this is consistent with the theory of Abakumov abak1 ; abak2 . The
formation of cluster dipole states is responsible for the observed significant
charge trapping at a lower voltage. Using both n-type and p-type detectors, we
find that holes are trapped more in an n-type detector and electrons are
trapped more in a p-type detector at 5.2 K. This phenomenon is attributed to a
larger probability of forming $D^{+^{*}}$ (or $A^{-^{*}}$) states than that of
$D^{-^{*}}$ (or $A^{+^{*}}$) states in an n-type (or a p-type) detector. These
cluster dipole states are thermally stable with a binding energy, which is
greater than $k_{B}$T at a level of 0.45 meV at 5.2 K. The amount of charge
trapping as a function of the external field can be related to the charge
trapping length, charge trapping cross sections, and the binding energy of the
excited dipole states, which is beyond the scope of this work and will be
reported in the follow-up papers.

The data that supports the findings of this study are available within the
article. The authors would like to thank Christina Keller for a careful
reading of this manuscript. This work was supported in part by NSF OISE
1743790, DE-SC0004768, and the State of South Dakota via a research center.

## References

  * (1) C. E. Aalseth et al., “Search for an Annual Modulation in a p-Type Point Contact Germanium Dark Matter Detector,” Phys. Rev. Lett. 107, 141301 (2011).
  * (2) Z. Ahmed et al., “Results from a Low-Energy Analysis of the CDMS II Germanium Data,” Phys. Rev. Lett. 106, 131302 (2011).
  * (3) R. Agnese et al., “Search for Low-Mass WIMPs with SuperCDMS,” Phys.Rev.Lett. 112 (2014) 241302.
  * (4) E. Armengaud et al., “A search for low-mass WIMPs with EDELWEISS-II heat-and-ionization detectors,” Phys. Rev. D86, 051701 (R) (2012).
  * (5) W. Zhao et al., “First results on low-mass WIMPs from the CDEX-1 experiment at the China Jinping underground laboratory,” Phys. Rev. D 88, (2013) 052004 .
  * (6) H.V. Klapdor-Kleingrothaus et al., “Latest results from the Heidelberg-Moscow double beta decay experiment,” Published in Eur. Phys. J. A12 (2001) 147-154.
  * (7) C. E. Aalseth et al., ),“The Igex 76Ge Neutrinoless Double-Beta Decay Experiment: Prospects for Next Generation Experiments,”Phys. Rev. D65 (2002) 092007.
  * (8) M. Agostini et al., “Results on Neutrinoless Double-$\beta$ Decay of Ge-76 from GERDA Phase I ,” Phys. Rev. Lett. 111, 122503.
  * (9) N. Abgrall et al., “The MAJORANA DEMONSTRATOR Neutrinoless Double-Beta Decay Experiment,” Advances in High Energy Physics, Volume 2014 (2014), Article ID 365432, 18 pages.
  * (10) R. Essig, J. Mardon, and T. Volansky, “Direct Detection of Sub-GeV Dark Matter, ”Phys. Rev. D 85 (2012) 076007.
  * (11) Z. Ahmed et al., “Search for Low-Mass WIMPs with SuperCDMS,” Phys.Rev.Lett. 112 (2014) 241302.
  * (12) D.-M. Mei et al., ”Direct detection of MeV-scale dark matter utilizing germanium internal amplification for the charge created by the ionization of impurities,” Eur. Phys. J. C (2018) 78:187.
  * (13) N. Abgrall et al., ”LEGEND-1000 Preconceptual Design”, arXiv: 2107.11462.
  * (14) V. N. Abakumov et al., ”Nonradiative Recombination in Semiconductors.” Sov. Phys. Semicond., Vol. 33. North-Holland, 1991.
  * (15) V. N. Abakymov et al., ”Nonradiative Recombination in Semiconductors.” Modern Problems in Condensed Matter Sciences, Vol. 33. North-Holland, 1991.
  * (16) G. Sadasiv, _Magnetoresistance in Germanium in the Impurity Conduction Range,_ Phys. Rev. 128, (1962) 1131.
  * (17) D. Vénos et al., _The behaviour of HPGe detectors operating at temperatures below 77 K,_ Nncl. Instr. Meth. in Phys. Res. A 454 (2000) 403-408.
  * (18) D. Neamen, _Semiconductor Physics and Devices_ , 3rd edition. New York: McGraw-Hill, 2003.
  * (19) B. G. Streetman, _Solid State Electronic Devices_ , 6th edition, Upper Saddle River, NJ: Prentice-Hall, Inc., 2006.
  * (20) L. Onsager, _Deviations from Ohm’s law in weak electrolytes_ , The Journal of Chemical Physics 2 (1934) 599 -615.
  * (21) L. Onsager, _Initial recombination of ions_ , Phys. Rev. 54 (1938) 554 - 557.
  * (22) U. Albrecht and H. Böassler, Phys. Status Solidi B 191, (1995) 455.
  * (23) D.-M. Mei et al. _Impact of charge trapping on the energy resolution of the Ge detectors for rare-event physics searches_ , 2020 J. Phys. G: Nucl. Part. Phys. 47 105106.
  * (24) M. Lax, _Cascade Capture of Electrons in Solids_ , Phys. Rev. 119, 15021523 (1960).
  * (25) J. Bardeen and W. Shockley, _Deformation Potentials and Mobilities in Non-Polar Crystals_ , Phys. Rev. 80 (1950)72.
  * (26) E. M. Gershenzon et al., ”Kinetics of electron and hole binding into excitons in germanium”, Zh. Eksp. Teor. Fiz. 84, 640-65 (1983).
  * (27) G.-J. Wang et al., _Crystal growth and detector performance of large size high-purity Ge crystals_ , _Material Science in Semiconductor Processing_ 39 (2015) 54-60.
  * (28) G.-J. Wang et al., _Development of large size high-purity germanium crystal growth,_ _Journal of Crystal Growth,_ 352 (1), (2012) 27-30.
  * (29) G.-J. Wang et al., _Dislocation density control in high-purity germanium crystal growth,_ _Journal of Crystal Growth_ , 393 (2014)54-58.
  * (30) X.-H. Mang et al., _Fabrication and Characterization High-Purity Germanium Detectors with Amorphous Germanium Contacts,_ _Journal of Instrumentation_ , 14 (2019) P02019.
  * (31) W.-Z. Wei et al., _The impact of the charge barrier height on germanium (Ge) detectors with amorphous-Ge contacts for light dark matter searches,_ _Eur. Phys. J. C_ , 80 (2020) 472.
  * (32) W.-Z. Wei et al., _Investigation of Amorphous Germanium Contact Properties with Planar Detectors Made from Home-Grown Germanium Crystals,_ _Journal of Instrumentation_ , 13 (2018) p012026.
  * (33) D. Vénos, et al., _Performance of HPGe detectors in the temperture region 2- 77 K_ , Nucl. Instr. and Meth. A 365 (1995) 419.
  * (34) Arran Thomas James Phipps, _Ionization Collection in Detectors of the Cryogenic Dark Matter Search,_ PhD thesis, University of California, Berkeley, 2016.
  * (35) V. Abakumov, V. I. Perel, and I. Yassievich, _Nonradiative recombination in semiconductors_ , 1st edition, Elsevier, July 25, 1991.
  * (36) K. Sundqvist, _Carrier transport and related effects in Detectors of Cryogenic Dark Matter Search,_ PhD thesis, University of California, Berkeley, 2012.
  * (37) K. M. Sundqvist, A. Phipps, A. V. Dixit $\&$ B. Sadoulet, ”Transport and Two-Species Capture of Electrons and Holes in Ultrapure Germanium at MilliKelvin Temperature,” Journal of Low Temperature Physics volume 176, pages 188-193 (2014).


# On Random Subset Generalization Error Bounds and the Stochastic Gradient
Langevin Dynamics Algorithm

Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund
Division of Information Science and Engineering (ISE)
KTH Royal Institute of Technology
{borjarg, germanb, ragnart<EMAIL_ADDRESS>This work was supported in part
by the Knut and Alice Wallenberg Foundation, the Swedish Foundation for
Strategic Research, and the Swedish Research Council.

(August 2020)

###### Abstract

In this work, we unify several expected generalization error bounds based on
random subsets using the framework developed by Hellström and Durisi [1].
First, we recover the bounds based on the individual sample mutual information
from Bu et al. [2] and on a random subset of the dataset from Negrea et al.
[3]. Then, we introduce their new, analogous bounds in the randomized
subsample setting from Steinke and Zakynthinou [4], and we identify some
limitations of the framework. Finally, we extend the bounds from Haghifam et
al. [5] for Langevin dynamics to stochastic gradient Langevin dynamics and we
refine them for loss functions with potentially large gradient norms.

##  I Introduction

A learning algorithm $\mathbb{A}$ is a mechanism that takes as an input a
sequence $S=(Z_{1},\ldots,Z_{N})$ of $N$ i.i.d. samples $Z_{i}\in\mathcal{Z}$
from $P_{Z}$, or a _dataset_ , and outputs a _hypothesis_ $W\in\mathcal{W}$ by
means of the conditional probability distribution $P_{W|S}$.

We measure how well a hypothesis $W$ describes a sample $Z$ using a loss
function $\ell:\mathcal{W}\times\mathcal{Z}\rightarrow\mathbb{R}^{+}$. Hence,
a hypothesis describes the samples from a population $P_{Z}$ well when its
_population risk_ , i.e.,
$L_{P_{Z}}(W)\triangleq\mathbb{E}_{P_{Z}}[\ell(W,Z)],$ is low. However,
$P_{Z}$ is often not available and we consider instead the _empirical risk_ on
the dataset $S$, i.e.,
$L_{S}(W)\triangleq\frac{1}{N}\sum_{i=1}^{N}\ell(W,Z_{i}),$ as a proxy.
Therefore, it is of interest to study the discrepancy between the population
and empirical risks, which is defined as the _generalization error_ :

$\textnormal{gen}(W,S)\triangleq L_{P_{Z}}(W)-L_{S}(W).$

By characterizing the generalization error of learning algorithms, we can
intuit how far the empirical risk is from the real population risk. Classical
approaches have bounded the generalization error in expectation and in
probability (PAC Bayes) either by measuring the complexity of the hypothesis
space $\mathcal{W}$ or by exploring properties of the learning algorithm
itself (see [6] for an overview of traditional approaches).

More recently, Xu and Raginsky [7], based on [8], found that the expected
generalization error $\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}$
is bounded from above by a function that depends on the mutual information
between the hypothesis $W$ and the dataset $S$ with which it is trained, i.e.,
$I(W;S)$. Similarly, Bu et al. [2] and Negrea et al. [3] found that it is also
bounded from above by a function that depends on the dependency between the
hypothesis and an individual sample, $I(W;Z_{i})$, and on the hypothesis and a
subset $S_{J}$ of the dataset
$D_{\textnormal{KL}}\big{(}P_{W|S}\>\big{\|}\>P_{\smash{W|S_{J^{c}}}}\big{)}$.

After that, Steinke and Zakynthinou [4] introduced a more structured setting.
They consider a super-sample of $2N$ i.i.d. samples $\tilde{Z}_{i}$ from
$P_{Z}$, i.e., $\tilde{S}=(\tilde{Z}_{1},\ldots,\tilde{Z}_{2N})$. This super-
sample is then used to construct the dataset $S$ by choosing between the
samples $\tilde{Z}_{i}$ and $\tilde{Z}_{i+N}$ using a Bernoulli random
variable $U_{i}$ with probability $1/2$; i.e., $Z_{i}=\tilde{Z}_{i+U_{i}N}$.
In this paper, we will distinguish between these two settings as the _standard
setting_ and the _randomized subsample setting_.111Note that in [1], the
latter is called the random-subset setting. However, this may cause confusion
with the random subset bounds in the present work.

In the randomized subsample setting, we can define the _empirical
generalization error_ as the difference between the empirical risk on the
samples from $\tilde{S}$ not used to obtain the hypothesis $W$ from the
algorithm, i.e., $\bar{S}=\tilde{S}\setminus S$, and the empirical risk on the
dataset $S$; i.e.,

$\widehat{\textnormal{gen}}(W,\tilde{S},U)\triangleq\frac{1}{N}\\!\sum_{i=1}^{N}\\!\Big{(}\ell\big{(}W,\tilde{Z}_{i+(1-U_{i})N}\big{)}\\!-\ell\big{(}W,\tilde{Z}_{i+U_{i}N}\big{)}\\!\Big{)}.$

Then, we may note that the expected value of the empirical and the (standard)
generalization errors coincide; i.e.,
$\mathbb{E}_{P_{\smash{W,\tilde{S},U}}}\big{[}\widehat{\textnormal{gen}}(W,\tilde{S},U)\big{]}=\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}$,
where $U$ is the sequence of $N$ i.i.d. Bernoulli trials $U_{i}$. Moreover, it
was also shown that the expected generalization error is bounded from above by
a function of the conditional mutual information between the hypothesis $W$
and the Bernoulli trials $U$, given the super-sample $\tilde{S}$ [4], i.e.,
$I(W;U|\tilde{S})$, and by a subset $U_{J}$ of the Bernoulli trials [5], i.e.,
$D_{\textnormal{KL}}\big{(}P_{\smash{W|U,\tilde{S}}}\>\big{\|}\>P_{\smash{W|U_{J^{c}},\tilde{S}}}\big{)}$.

A first step towards unifying these results was given by Hellström and Durisi
[1], who introduced a framework that allowed them to recover the mutual
information $I(W;S)$ and conditional mutual information $I(W;U|\tilde{S})$
expected generalization error bounds, among other PAC-Bayesian bounds. In this
work, we show that the aforementioned framework can also be adapted to obtain
bounds based on a random subset of the dataset. In particular:

  1. (i)

We recover the bounds based on the individual sample mutual information [2,
Proposition 1] and on a random subset $S_{J}$ of the dataset [3, Theorem 2.4].
These results are presented in Propositions 1 and 2.

  2. (ii)

We obtain new bounds based on the “individual sample” conditional mutual
information $I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})$ and on a random subset
$U_{J}$ of the Bernoulli trials. These results are presented in Propositions 3
and 4.

  3. (iii)

We further show that tighter bounds of the type of [3, Theorem 2.5] and [5,
Theorem 3.7] cannot be recovered with this framework.

Secondly, we develop expected generalization error bounds for the stochastic
gradient Langevin dynamics (SGLD) algorithm. More specifically,

  1. (iv)

We extend [5, Theorem 3.7] in Proposition 5 in order to generalize the bound
from [5, Theorem 4.2] for Langevin dynamics to SGLD in Proposition 6, and to
obtain the new bound in Proposition 7 using [9, Lemma 2]. Then, we combine
Propositions 6 and 7 to generate our tightest bound on SGLD in Corollary 2.

##  II Preliminaries

####  II-1 Notation

Throughout this work, we write random variables in capital letters, $X$, and
their realizations in lowercase letters, $x$. We further write their target
spaces in calligraphic letters, $\mathcal{X}$, and the sigma algebras of their
target space in script-style letters, $\mathscr{X}$. We consider that all
random variables are functions $X:\Omega\rightarrow\mathcal{X}$ from an
abstract probability space $(\Omega,\mathcal{A},\mathbb{P})$ to a target space
$(\mathcal{X},\mathscr{X})$. Then, we denote their probability distribution by
$P_{X}:\mathscr{X}\rightarrow[0,1]$, where $P_{X}(B)=\mathbb{P}(X\in B)$ for
all $B\in\mathscr{X}$.

When we consider more than one random variable, e.g., $X$ and $Y$, we write
their joint probability distribution as
$P_{X,Y}:\mathscr{X}\otimes\mathscr{Y}\rightarrow[0,1]$ and their product
distribution as $P_{X}\times
P_{Y}:\mathscr{X}\otimes\mathscr{Y}\rightarrow[0,1]$. Moreover, we also write
the conditional distribution of $Y$ given $X$ as
$P_{Y|X}:\mathscr{Y}\times\mathcal{X}\rightarrow[0,1]$, which defines a
probability distribution $P_{Y|X=x}$ over $(\mathcal{Y},\mathscr{Y})$ for each
element $x\in\mathcal{X}$. Finally, we abuse notation and write $P_{Y|X}\times
P_{X}=P_{X,Y}$ since
$P_{X,Y}(B)=\int\big{(}\int\chi_{B}\big{(}(x,y)\big{)}dP_{Y|X=x}(y)\big{)}dP_{X}(x)$
for all $B\in\mathscr{X}\otimes\mathscr{Y}$, where $\chi_{B}$ is the
characteristic function of the set $B$.

The relative entropy between two probability distributions $P$ and $Q$ is
defined as

$D_{\textnormal{KL}}(P\>\|\>Q)\triangleq\mathbb{E}_{P}\left[\log\frac{dP}{dQ}\right],$

where $dP/dQ$ is the Radon–Nikodym derivative. When one of the two
distributions, $P$ or $Q$, depends on a random variable $R$, e.g.,
$P(R)=P_{X|R}$, then the relative entropy between the said distributions is
also dependent on the random variable $R$. For instance, in this example
$D_{\textnormal{KL}}(P(R)\>\|\>Q)=f(R)$. To say that $P$ is absolutely
continuous w.r.t. $Q$ we write $P\ll Q$.

####  II-2 A helpful Lemma

We abstract and summarize the results from [1, Theorem 1 and Corollary 1, and
Theorem 4 and Corollary 5] in the following Lemma.

######  Lemma 1.

Let $f:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ either:

  1. (i)

have zero mean and be $\sigma$-subgaussian under $P_{X}$ for all
$y\in\mathcal{Y}$, or

  2. (ii)

have zero mean and be $\sigma$-subgaussian under $P_{X}\times P_{Y}$.

Then, for all distributions $Q_{Y}$ over $(\mathcal{Y},\mathscr{Y})$,

$\big{|}\mathbb{E}_{P_{X,Y}}[f(X,Y)]\big{|}\leq\sqrt{2\sigma^{2}D_{\textnormal{KL}}(P_{X,Y}\>\|\>Q_{Y}\times
P_{X})}.$ (1)

##  III Subset Bounds

In this section, we use Lemma 1 to derive several expected generalization
error bounds based on random subsets. We recover known bounds for the standard
setting and we also obtain their randomized subsample setting counterparts.

###  III-A Achievable subset bounds

In the standard setting, the bounds using the individual sample mutual
information, $I(W;Z_{i})$, from Bu et al. [2, Proposition 1] and the random
subset from Negrea et al. [3, Theorem 2.4] can be recovered using the
framework from [1] taking advantage of the subgaussianity of the empirical
risk $L_{S_{J}}(W)$, of a subset $S_{J}$ of the dataset, under $P_{S_{J}}$.

######  Proposition 1 ([2, Proposition 1]).

Under the assumptions of the standard setting, if $P_{W,Z_{i}}\ll P_{W}\times
P_{Z}$ for all $i$ and either

  1. (i)

$\ell(w,Z)$ is $\sigma$-subgaussian under $P_{Z}$ for all $w\in\mathcal{W}$ or

  2. (ii)

$\ell(W,Z)$ is $\sigma$-subgaussian under $P_{W}\times P_{Z}$,

then the expected generalization error is bounded as follows:

$\big{|}\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\big{|}\leq\frac{1}{N}\sum_{i=1}^{N}\sqrt{2\sigma^{2}I(W;Z_{i})}.$
(2)

###### Sketch of the alternative proof.

In the setting of Lemma 1, let
$f(X,Y)=\textnormal{gen}_{i}(W,Z_{i})\triangleq\mathbb{E}_{P_{Z}}[\ell(W,Z)]-\ell(W,Z_{i})$,
$P_{X}=P_{Z}=P_{Z_{i}}$, and $P_{Y}=Q_{Y}=P_{W}$. Then, we have that

$\left|\mathbb{E}_{P_{W,\smash{Z_{i}}}}\big{[}\textnormal{gen}_{i}(W,Z_{i})\big{]}\right|\leq\sqrt{2\sigma^{2}I(W;Z_{i})}.$

Finally, we note that
$\mathbb{E}_{P_{W,S}}[\ell(W,Z_{i})]=\mathbb{E}_{P_{W,Z_{i}}}[\ell(W,Z_{i})]$
and we use the triangle inequality to obtain the desired result. ∎

######  Proposition 2 (Extension of [3, Theorem 2.4]).

Consider the assumptions of the standard setting. Also consider a random
subset $J\subseteq[N]$ such that $|J|=M$, which is uniformly distributed and
independent of $W$ and $S$, and a random variable $R$ which is independent of
$S$ and $J$. If $P_{W,S_{J}|S_{J^{c}},R}\ll Q_{W|S_{J^{c}},R}\times P_{S_{J}}$
for all $J$,222We note that $Q_{W|S_{J^{c}},R}$ might differ from
$P_{W|S_{J^{c}},R}$, the marginal of $P_{W,S_{J}|S_{J^{c}},R}$ with respect to
$W$. and either:

  1. (i)

$\ell(w,Z)$ is $\sigma$-subgaussian under $P_{Z}$ for all $w\in\mathcal{W}$ or

  2. (ii)

$\ell(W,Z)$ is $\sigma$-subgaussian under $P_{W|S_{J^{c}},R}\times P_{Z}$,

then the expected generalization error is bounded as follows:

$\displaystyle\big{|}\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\big{|}$
$\displaystyle\leq\mathbb{E}\Bigg{[}\sqrt{\frac{2\sigma^{2}}{M}D_{\textnormal{KL}}\big{(}P_{W,S_{J}|S_{J^{c}},R}\>\big{\|}\>Q_{W|S_{J^{c}},R}\times
P_{S_{J}}\big{)}}\Bigg{]},$ (3)

where $Q_{W|S_{J^{c}},R}$ is a
$(\mathscr{Z}^{\otimes(N-M)}\otimes\mathscr{R}\otimes\mathscr{J})$-measurable
distribution over $(\mathcal{W},\mathscr{W})$, and the expectation on the
r.h.s. of (3) is over $P_{J,S_{J^{c}},R}$.

###### Sketch of the alternative proof.

In the setting of Lemma 1 and assuming a fixed $J$, let
$f(X,Y)=\textnormal{gen}_{J}(W,S_{J})\triangleq\mathbb{E}_{P_{Z}}[\ell(W,Z)]-\frac{1}{M}\sum_{i\in
J}\ell(W,Z_{i})$, $P_{X}=P_{S_{J}}$, and $P_{Y}=P_{W|S_{J^{c}},R}$. Then,
since $\textnormal{gen}_{J}$ is $\sigma/\sqrt{M}$-subgaussian and zero-mean
under $P_{S_{J}}$, we have that,

$\big{|}\mathbb{E}_{P_{W,S_{J}|S_{J^{c}},R}}\big{[}\textnormal{gen}_{J}(W,S_{J})\big{]}\big{|}\\\
\leq\sqrt{\frac{2\sigma^{2}}{M}D_{\textnormal{KL}}\big{(}P_{W,S_{J}|S_{J^{c}},R}\>\big{\|}\>Q_{W|S_{J^{c}},R}\times
P_{S_{J}}\big{)}}.$

Then, by Jensen’s inequality,
$|\mathbb{E}_{P_{W,S,R,J}}[\textnormal{gen}_{J}(W,S_{J})]|\leq\mathbb{E}_{P_{J,S_{J^{c}},R}}[|\mathbb{E}_{P_{W,S_{J}|S_{J^{c}},R}}[\textnormal{gen}_{J}(W,S_{J})]|]$,
which completes the proof of the Proposition. ∎

######  Remark 1.

Note that in [3, Theorem 2.4] the result is formulated in terms of the
complementary random subset $J\leftarrow J^{c}$; we use this other formulation
instead to maintain the notation throughout the paper. Moreover, we prove that
(3) also holds for condition (ii), which is not implied by condition (i) [3,
Appendix C], and also avoid forfeiting the absolute value.

In the sequel, we find a new bound based on the individual sample conditional
mutual information $I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})$, which is the
tightest mutual-information–based bound in this setting (see Appendix -J), and
on random subsets of the data. For this task, we must take advantage of the
subgaussianity of the difference of the empirical risks
$L_{\smash{\bar{S}}_{J}}(W)-L_{S_{J}}(W)$ of subsets (indexed by $J$) of the
dataset $S$ and the rest of the super-sample $\bar{S}=\tilde{S}\setminus S$,
under $P_{U_{J}}$.

######  Proposition 3 (Individual conditional mutual information bound).

Under the assumptions of the randomized subsample setting, if
$P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}}}\ll
P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N}}}\times P_{U_{i}}$ for all $i$ and
$\ell(w,z)$ is bounded in $[a,b]$ for all $w\in\mathcal{W}$ and
$z\in\mathcal{Z}$, then the expected generalization error is bounded as
follows:

$\left|\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\right|\\\
\leq\frac{1}{N}\sum_{i=1}^{N}\sqrt{2(b-a)^{2}I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})}.$
(4)

###### Sketch of the proof.

In the setting of Lemma 1, let
$f(X,Y)=\widehat{\textnormal{gen}}_{i}\big{(}W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}\big{)}\triangleq\ell\big{(}W,\tilde{Z}_{i+(1-U_{i})N}\big{)}-\ell\big{(}W,\tilde{Z}_{i+U_{i}N}\big{)}$,
$P_{X}=P_{U_{i}}$, and
$P_{Y}=Q_{Y}=P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N}}}$. Then, since
$\widehat{\textnormal{gen}}_{i}$ is zero-mean and $(b-a)$-subgaussian (since
it is bounded in $[a-b,b-a]$) under $P_{U_{i}}$, we have that

$\big{|}\mathbb{E}_{P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}}}}\big{[}\widehat{\textnormal{gen}}_{i}\big{(}W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}\big{)}\big{]}\big{|}\\\
\leq\sqrt{2(b-a)^{2}I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})}.$

If we use that $\big{|}\sum_{i=1}^{N}x_{i}\big{|}\leq\sum_{i=1}^{N}|x_{i}|$
and note that

$\mathbb{E}_{P_{W,\smash{\tilde{S}},U}}\big{[}\widehat{\textnormal{gen}}\big{(}W,\tilde{S},U\big{)}\big{]}\\\
=\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}}}}\big{[}\widehat{\textnormal{gen}}_{i}\big{(}W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}\big{)}\big{]},$

we obtain the bound (4). ∎

######  Proposition 4.

Consider the assumptions of the randomized subsample setting. Also consider a
subset $J\subseteq[N]$ such that $|J|=M$, which is uniformly distributed and
independent of $W$, $\tilde{S}$, and $U$, and a random variable $R$ which is
independent of $\tilde{S}$, $J$, and $U$. If
$P_{\smash{W,U_{J}|U_{J^{c}},\tilde{S},R}}\ll Q\times P_{U_{J}}$ for all $J$
and $\ell(w,z)$ is bounded in $[a,b]$ for all $w\in\mathcal{W}$ and
$z\in\mathcal{Z}$, then the expected generalization error is bounded as
follows:

$\displaystyle\big{|}\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\big{|}$
$\displaystyle\leq\mathbb{E}\bigg{[}\sqrt{\frac{2(b-a)^{2}}{M}D_{\textnormal{KL}}\big{(}P_{\smash{W,U_{J}|U_{J^{c}},\tilde{S},R}}\>\big{\|}\>Q\times
P_{U_{J}}\big{)}}\bigg{]},$ (5)

where $Q=Q_{\smash{W|U_{J^{c}},\tilde{S},R}}$ is a
$(\mathscr{U}^{\otimes(N-M)}\otimes\mathscr{Z}^{\otimes
2N}\otimes\mathscr{R}\otimes\mathscr{J})$-measurable distribution over
$(\mathcal{W},\mathscr{W})$, and the expectation on the r.h.s. of (5) is with
respect to $P_{\smash{J,U_{J^{c}},\tilde{S},R}}$.

###### Sketch of the proof.

In the setting of Lemma 1 and assuming a fixed $J$, let
$f(X,Y)=\widehat{\textnormal{gen}}_{J}\big{(}W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N}\big{)}\triangleq\frac{1}{M}\sum_{i\in
J}\big{[}\ell\big{(}W,\tilde{Z}_{i+(1-U_{i})N}\big{)}-\ell\big{(}W,\tilde{Z}_{i+U_{i}N}\big{)}\big{]}$,
$P_{X}=P_{U_{J}}$, and $P_{Y}=P_{\smash{W|U_{J^{c}},\tilde{S},R}}$. Since each
of the $M$ summands of $\widehat{\textnormal{gen}}_{J}$ is zero-mean and
bounded in $[a-b,b-a]$ under $P_{U_{J}}$, then
$\widehat{\textnormal{gen}}_{J}$ is zero-mean and $(b-a)/\sqrt{M}$-subgaussian
under $P_{U_{J}}$. Therefore, we have that

$\displaystyle\big{|}\mathbb{E}_{P_{\smash{W,U_{J}|U_{J^{c}},\tilde{S},R}}}\big{[}\widehat{\textnormal{gen}}_{J}\big{(}W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N}\big{)}\big{]}\big{|}$
$\displaystyle\leq\sqrt{\frac{2(b-a)^{2}}{M}D_{\textnormal{KL}}\big{(}P_{\smash{W,U_{J}|U_{J^{c}},\tilde{S},R}}\>\big{\|}\>Q_{\smash{W|U_{J^{c}},\tilde{S},R}}\times
P_{U_{J}}\big{)}}.$

By Jensen’s inequality,
$|\mathbb{E}_{P_{\smash{W,\tilde{S},U,R,J}}}[\widehat{\textnormal{gen}}_{J}(W,U_{J}\tilde{S}_{J},\tilde{S}_{J+N})]|\allowbreak\leq\mathbb{E}_{P_{\smash{J,U_{J^{c}},\tilde{S},R}}}[|\mathbb{E}_{P_{\smash{W,U_{J}|U_{J^{c}},\tilde{S},R}}}[\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})]|]$
and the proof of the Proposition is complete. ∎

######  Remark 2.

Note that a similar bound can be directly obtained combining a slight
modification of [5, Theorem 3.1] (where $R$ is included) and [5, Lemma 3.6].
However, this approach results in a bound without the absolute value.

###  III-B Non-achievable subset bounds

Despite its versatility, the present framework does not allow us to obtain
bounds where all the expectations are outside of the square root, such as [3,
Theorem 2.5] or [5, Theorem 3.7]. If we look at (1), we see that the term
$D_{\textnormal{KL}}(P_{X,Y}\>\|\>Q_{Y}\times P_{X})$, which can also be
written as $\mathbb{E}_{P_{X}}[D_{\textnormal{KL}}(P_{Y|X}\>\|\>Q_{Y})]$, is
inside the square root; hence, Jensen’s inequality prevents us from taking the
expectation with respect to $P_{X}$ ($P_{S_{J}}$ or $P_{U_{J}}$ in our case)
outside the concave square root function.

In particular, a tighter (when $M=1$) version of [3, Theorem 2.4] is found in
[3, Theorem 2.5], with the same conditions as Proposition 2, except that
$\ell(w,z)$ is now required to be bounded in $[a,b]$; namely

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\\\
\leq\frac{b-a}{\sqrt{2}}\
\mathbb{E}_{P_{J,S,R}}\bigg{[}\sqrt{D_{\textnormal{KL}}\big{(}P_{W|S,R}\>\big{\|}\>Q_{\smash{W|S_{J^{c}},R}}\big{)}}\bigg{]}.$
(6)

In the same spirit, a tighter version of Proposition 4 is [5, Theorem 3.7],
from which we present a slight extension, as it will be needed for the bounds
on the stochastic gradient Langevin dynamics algorithm in the following
section.

######  Proposition 5 (Extension of [5, Theorem 3.7]).

Consider the assumptions of the randomized subsample setting. Also consider a
subset $J\subseteq[N]$ such that $|J|=M$, which is uniformly distributed and
independent of $W$, $\tilde{S}$, and $U$, and a random variable $R$ which is
independent of $\tilde{S}$, $J$, and $U$. If $P_{\smash{W|U,\tilde{S},R}}\ll
Q_{\smash{W|U_{J^{c}},\tilde{S},R}}$ for all $J$ and $\ell(w,z)$ is bounded in
$[a,b]$ for all $w\in\mathcal{W}$ and $z\in\mathcal{Z}$, then the expected
generalization error is bounded as follows:

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\sqrt{2}(b-a)\\\
\mathbb{E}_{P_{\smash{J,\tilde{S},U,R}}}\bigg{[}\sqrt{D_{\textnormal{KL}}\big{(}P_{\smash{W|U,\tilde{S},R}}\>\big{\|}\>Q_{\smash{W|U_{J^{c}},\tilde{S},R}}\big{)}}\bigg{]},$
(7)

where $Q_{\smash{W|U_{J^{c}},\tilde{S},R}}$ is a
$(\mathscr{U}^{\smash{\otimes(N-M)}}\otimes\mathscr{Z}^{\otimes
2N}\otimes\mathscr{R}\otimes\mathscr{J})$-measurable distribution over
$(\mathcal{W},\mathscr{W})$.

###### Proof.

The extension follows trivially from the proof of Theorem 3.7 on [5]. The
random variable $R$ is incorporated using the Donsker–Varadhan variational
formula [10, Theorem 3.5] with the probability distributions
$P(\tilde{S},U,R)$ and $Q(\tilde{S},U_{J},J,R)$ instead of $P(\tilde{S},U)$
and $Q(\tilde{S},U_{J},J)$. Then, the term $(b-a)$ results from the
boundedness of the Donsker–Varadhan variational function. Finally, the
extension to arbitrary sizes of the subset $J$ is already included in the
original proof in [5, Appendix D]. ∎

######  Remark 3.

In Propositions 2 and 4, as well as in (6) and Proposition 5, when $M=1$,
similarly to Propositions 1 and 3, the outermost expectation with respect to
$J$ is equivalent to a sum over all the indices $i\in[N]$ divided by $N$. That
is, $\mathbb{E}_{J}[f(J)]=\frac{1}{N}\sum_{i=1}^{N}f(i)$.

##  IV Bounds on Noisy Iterative Algorithms

In this section, we leverage the bound from Proposition 5, not based on Lemma
1, to extend the result on Langevin dynamics from [5, Theorem 4.2] to
stochastic gradient Langevin dynamics. After that, we propose an alternative
for such extension for algorithms with large Lipschitz constant or large
discrepancy between the gradients of two samples. Finally, we combine both
bounds to generate a refined version that better exploits the samples’ and
hypotheses’ trajectory knowledge.

###  IV-A Stochastic gradient Langevin dynamics algorithm

The stochastic gradient Langevin dynamics (SGLD) algorithm is an iterative
procedure to learn a parametrized hypothesis $W_{\theta}$ from a dataset $S$.
More specifically, SGLD works for hypotheses that are completely characterized
by a parameter $\theta\in\mathbb{R}^{d}$. The algorithm starts with a random
initialization, $\theta_{0}$, of the parameter. Then, at each iteration
$t\in[T]$, it samples a random batch $S_{V_{t}}$ from the dataset $S$; updates
the previous parameter $\theta_{t-1}$ with a scaled $(-\eta_{t})$ version of
the gradient of the loss given that parameter and the random batch, i.e.,
$\nabla_{\theta_{t-1}}L_{S_{V_{t}}}(W_{\theta_{t-1}})$; and adds a scaled
$(\sigma_{t})$ isotropic Gaussian random noise
$\varepsilon_{t}\sim\mathcal{N}(0,I_{d})$. That is,

$\theta_{t}\leftarrow\theta_{t-1}-\eta_{t}\nabla_{\theta_{t-1}}L_{S_{V_{t}}}(W_{\theta_{t-1}})+\sigma_{t}\varepsilon_{t},$

where $W_{\theta_{t}}$ (or $W_{t}$) is the hypothesis at iteration $t$, and
$W_{\theta_{T}}$ is the final hypothesis of SGLD. When the batch is composed
of all samples, i.e., there is no stochasticity in the sample selection, the
algorithm is called Langevin dynamics (LD).

###  IV-B Expected generalization error bounds

######  Proposition 6 (Extension of [5, Theorem 4.2] to SGLD).

Under the conditions of the randomized subsample setting, if we assume that
the loss function $\ell(w,z)$ is bounded in $[a,b]$ for all $w\in\mathcal{W}$
and all $z\in\mathcal{Z}$, then the expected generalization error of the SGLD
is bounded as follows:

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\sqrt{2}(b-a)\\\
\mathbb{E}_{\smash{P_{1}}}\Bigg{[}\sqrt{\sum_{\smash{t\in\mathcal{T}_{J}(V^{T})}}\mathbb{E}_{\smash{P_{2}^{t}}}\bigg{[}\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}(U_{J}-\pi_{J,t})^{2}\bigg{]}}\Bigg{]},$
(8)

where $P_{1}=P_{\smash{J,\tilde{S},U,V^{T}}}$,
$P_{2}^{t}=P_{\smash{W^{t-1}|U,\tilde{S},V^{t-1}}}$, $|J|=1$, $|V_{t}|$ is the
cardinality of the batch, $\mathcal{T}_{J}\big{(}V^{T}\big{)}$ is the set of
iterations for which sample $J$ was included in the batches from $V^{T}$,
$\zeta_{J,t}\triangleq\nabla_{\theta_{t-1}}\ell(W_{\smash{\theta_{t-1}}},\tilde{Z}_{J})-\nabla_{\theta_{t-1}}\ell(W_{\smash{\theta_{t-1}}},\tilde{Z}_{J+N})$
is the two-sample incoherence at iteration $t$, and $\pi_{J,t}$ is an estimate
(based on the samples’ and hypotheses’ trajectory) of the probability that
$U_{J}=1$.

###### Sketch of the proof.

Similarly to the proof of Theorem 4.2 in [5], we start from the bound in
Proposition 5, where here we let $R$ be the full batch trajectory $V^{T}$, and
we use the fact that
$D_{\textnormal{KL}}\big{(}P_{\smash{W|U,\tilde{S},V^{T}}}\>\big{\|}\>Q_{\smash{W|U_{J^{c}},\tilde{S},V^{T}}}\big{)}\leq\sum_{t=1}^{T}\allowbreak\mathbb{E}_{\smash{P_{2}^{t}}}\big{[}D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}\big{]}$.
Then, as in [2], we restrict the sum to only the non-zero terms, that is
$\sum_{t=1}^{T}\mathbb{E}_{\smash{P_{2}^{t}}}\big{[}D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}\big{]}=\sum_{t\in\mathcal{T}_{J}(V^{T})}\\!\mathbb{E}_{\smash{P_{2}^{t}}}\\!\big{[}D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}\\!\big{]}$.
After that, similarly to [5], we note that
$P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}$ is a Gaussian distribution and
we then let $Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}$ be also a
Gaussian distribution, but with a different mean. The first distribution uses
$U_{J}$ to determine which gradient
$\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+U_{J}N})$ appears on
its mean, while the latter uses a weighted average of both gradients by means
of $\pi_{J,t}$. Finally, we use the analytical expression for the relative
entropy between two Gaussian distributions to obtain (8). ∎

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\sqrt{2}(b-a)\,\mathbb{E}_{P_{1}}\smash{\Bigg{[}\sqrt{\sum\nolimits_{t\in\mathcal{T}_{J}(V^{T})}\mathbb{E}_{P_{2}^{t}}\bigg{[}{-}\log\bigg{(}\big{|}U_{J}-\pi_{J,t}\big{|}\exp\Big{(}-\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}\Big{)}+\big{|}\bar{\pi}_{J,t}-U_{J}\big{|}\bigg{)}\bigg{]}}\Bigg{]}}$
(10)

######  Corollary 1.

Consider the setting of Proposition 6. In the case that $\ell$ is
$L$-Lipschitz, and if we assume that the batches have a constant size $K$, the
generalization error of the SGLD is bounded as follows:

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\frac{2L}{K}(b-a)\\\
\mathbb{E}_{P_{1}}\Bigg{[}\sqrt{\sum_{\smash{t\in\mathcal{T}_{J}(V^{T})}}\\!\\!\mathbb{E}_{P_{2}^{t}}\bigg{[}\frac{\eta_{t}^{2}}{\sigma_{t}^{2}}(U_{J}-\pi_{J,t})^{2}\bigg{]}}\Bigg{]}.$
(9)

The bound from Proposition 6 recovers [5, Theorem 4.2] for LD (i.e.,
$|V_{t}|=N$) and, for SGLD, it can be compared with other bounds. For
instance, under the assumptions from Corollary 1, if we compare it with [3,
Theorem 3.1]:

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\frac{L(b-a)}{\sqrt{2}K}\,\mathbb{E}_{P_{\smash{J,V^{T}}}}\Bigg{[}\sqrt{\sum_{\smash{t\in\mathcal{T}_{J}(V^{T})}}\\!\frac{\eta_{t}^{2}}{\sigma_{t}^{2}}}\Bigg{]},$

we note that (9) has a worse constant. However, if
$\mathbb{E}_{P_{2}^{t}}\big{[}(U_{J}-\pi_{J,t})^{2}\big{]}\leq 1/8$, the bound
from Corollary 1 is tighter. This is expected to happen after some iterations,
when a good estimate of $U_{J}$ is possible. The same happens when we assume
$M=1$ and compare it with [2, Proposition 3], where
$\mathbb{E}_{P_{2}^{t}}\big{[}(U_{J}-\pi_{J,t})^{2}\big{]}\leq 1/16$ is
required.

######  Remark 4.

The estimate $\pi_{J,t}$ is dependent on the samples’ and hypotheses’
trajectory. An example on how to build such an estimate, based on binary
hypothesis testing, is presented in [5] for LD. Adapted to SGLD, we let the
estimate $\pi_{J,t}$ be a function $\phi:\mathbb{R}\rightarrow[0,1]$ of the
log-likelihood ratio between the probability that $U_{J}=1$ and $U_{J}=0$,
based on $(W^{t-1},J,\tilde{S},U_{J^{c}},V^{t})$. That is,

$\displaystyle\pi_{J,t}$
$\displaystyle\triangleq\phi\left(\log\frac{P_{\smash{U_{J}|W^{t-1},\tilde{S},U_{J^{c}},V^{t}}}(1)}{P_{\smash{U_{J}|W^{t-1},\tilde{S},U_{J^{c}},V^{t}}}(0)}\right)$
$\displaystyle=\phi\left(\sum\nolimits_{t\in
T_{J}(V^{t})}\big{(}Y_{J,t,0}-Y_{J,t,1}\big{)}\right),$

where

$\displaystyle
Y_{J,t,u}=\frac{1}{2\sigma_{t}^{2}}\Big{\|}\theta_{t}{-}\theta_{t-1}{+}\frac{\eta_{t}}{|V_{t}|}\Big{(}\nabla_{\smash{\theta_{t-1}}}\ell\big{(}W_{\smash{\theta_{t-1}}},\tilde{Z}_{J+uN}\big{)}$
$\displaystyle+(|V_{t}|-1)\nabla_{\smash{\theta_{t-1}}}L_{S_{V_{t}\setminus
J}}(W_{\theta_{t-1}})\Big{)}\Big{\|}^{2}.$

A potential weakness in the bound from Proposition 6 is its linear dependence
with $\|\zeta_{J,t}\|$, which might make the bound loose if the Lipschitz
constant $L$ is large. As a remedy, we propose the following alternative.

######  Proposition 7.

Under the setting of Proposition 6, the expected generalization error of SGLD
is bounded as shown in (10) at the top of the page, where
$\bar{\pi}_{J,t}=1-\pi_{J,t}$.

###### Sketch of the proof.

We follow the steps of the proof of Proposition 6, but instead of considering
$Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}$ as a single Gaussian
distribution, we define it as a mixture of two Gaussians. The responsibility
of each mixture component is $\pi_{J,t}$ and $\bar{\pi}_{J,t}$ with either
$\nabla_{\theta_{t-1}}\ell\big{(}W_{\smash{\theta_{t-1}}},\tilde{Z}_{J+N}\big{)}$
or
$\nabla_{\theta_{t-1}}\ell\big{(}W_{\smash{\theta_{t-1}}},\tilde{Z}_{J}\big{)}$
appearing on their respective mean. Then, we apply [9, Lemma 2] to bound the
relative entropy
$D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}$,
and the rest follows by algebraic manipulation. ∎

For example, if $\pi_{J,t}=1/2$, which is a reasonable value during the first
iterations, the bound from Proposition 7 is tighter than the one from
Proposition 6 for $\|\zeta_{J,t}\|\gtrsim 2.21\sigma_{t}|V_{t}|/\eta_{t}$;
this may likely be the case when $\eta_{t}/\sigma_{t}\in\Theta(N^{\alpha/2})$,
for $\alpha\in(0,1)$, see e.g. [3, Appendix E]. In fact, for large values of
${\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}}$, e.g.,
when the Lipschitz condition is not met, the term inside the innermost
expectation in (10) tends to ${-}\log|\bar{\pi}_{J,t}-U_{J}|$ from below.

Moreover, we note that the only terms that change between (8) and (10) are the
summands inside the square root. These terms are obtained by considering
different data-dependent distributions
$Q_{\smash{W_{t}|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}$, which we can choose
arbitrarily at each iteration; hence, we may choose the tightest form for each
summand, as it is stated next.

######  Corollary 2.

Under the setting of Proposition 6, if we let

$\displaystyle f_{J,t}$
$\displaystyle\triangleq\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}(U_{J}-\pi_{J,t})^{2}\textnormal{
and }$ $\displaystyle g_{J,t}$
$\displaystyle\triangleq-\log\Big{(}|U_{J}-\pi_{J,t}|\smash{e^{-\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}}}+|\bar{\pi}_{J,t}-U_{J}|\Big{)},$

then the expected generalization error of SGLD is bounded as follows:

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\sqrt{2}(b-a)\\\
\mathbb{E}_{\smash{P_{1}}}\bigg{[}\sqrt{\sum\nolimits_{t\in\mathcal{T}_{J}(V^{T})}\mathbb{E}_{\smash{P_{2}^{t}}}\Big{[}\min\big{(}f_{J,t},\,g_{J,t}\big{)}\Big{]}}\bigg{]}.$
(11)

##  V Discussion

In this paper, we showed how the framework from [1] allows us to recover the
individual sample and subset bounds from [2] and [3], as well as to generate
their parallels in the randomized subsample setting from [4]. Moreover, we
showed why the framework does not allow us to obtain bounds with all the
expectations outside the square root, such as the tightest bounds from [3] and
[5]. Finally, we extended the LD bounds from [5] to SGLD and we refined them
to loss functions with potentially large gradient norms.

## References

  * Hellström and Durisi [2020] F. Hellström and G. Durisi, “Generalization bounds via information density and conditional information density,” _IEEE Journal on Selected Areas in Information Theory_ , pp. 1–1, 2020.
  * Bu et al. [2020] Y. Bu, S. Zou, and V. V. Veeravalli, “Tightening mutual information based bounds on generalization error,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 1, pp. 121–130, May 2020.
  * Negrea et al. [2019] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy, “Information-theoretic generalization bounds for SGLD via data-dependent estimates,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 11 015–11 025.
  * Steinke and Zakynthinou [2020] T. Steinke and L. Zakynthinou, “Reasoning about generalization via conditional mutual information,” in _Conference on Learning Theory_ , ser. Proceedings of Machine Learning Research, vol. 125, Jul. 2020, pp. 3437–3452.
  * Haghifam et al. [2020] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite, “Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms,” in _Advances in Neural Information Processing Systems_ , 2020.
  * Shalev-Shwartz and Ben-David [2014] S. Shalev-Shwartz and S. Ben-David, _Understanding machine learning: From theory to algorithms_. Cambridge university press, 2014.
  * Xu and Raginsky [2017] A. Xu and M. Raginsky, “Information-theoretic analysis of generalization capability of learning algorithms,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 2524–2533.
  * Russo and Zou [2020] D. Russo and J. Zou, “How much does your data exploration overfit? controlling bias via information usage,” _IEEE Transactions on Information Theory_ , vol. 66, no. 1, pp. 302–323, Jan. 2020.
  * Rodríguez-Gálvez et al. [2020] B. Rodríguez-Gálvez, G. Bassi, and M. Skoglund, “Upper bounds on the generalization error of private algorithms,” _arXiv:2005.05889 [cs, stat]_ , May 2020.
  * Polyanskiy and Wu [2012–2017] Y. Polyanskiy and Y. Wu, “Lecture notes on Information Theory,” _MIT (6.441), UIUC (ECE 563), Yale (STAT 664)_ , 2012–2017.

###  -A Details of Lemma 1

Before starting with the proof of the Lemma, we introduce the _information
density_ between two random variables $X$ and $Y$, which is defined as

$\iota(X;Y)\triangleq\log\frac{dP_{X,Y}}{d(P_{X}\times P_{Y})},$

and the _conditional information density_ between two random variables $X$ and
$Y$ given a random variable $Z$, which is defined as

$\iota(X;Y|Z)\triangleq\log\frac{dP_{X,Y|Z}}{d(P_{X|Z}\times P_{Y|Z})}.$

Note that if we consider two random variables $X$ and $Y|Z$, where $Y|Z$ is a
random variable described by the conditional probability distribution
$P_{Y|Z}$, and where $X$ is independent of $Z$, then their information density
$\iota(X;(Y|Z))$ is equal to the conditional information density between $X$
and $Y$ given $Z$, $\iota(X;Y|Z)$, i.e.,

$\log\frac{dP_{X,Y|Z}}{d(P_{Y|Z}\times P_{X})}.$

###### Proof of Lemma 1.

If (i) holds, i.e., $f(X,y)$ is $\sigma$-subgaussian under $P_{X}$ for all
$y\in\mathcal{Y}$ and we know that $\mathbb{E}_{P_{X}}\big{[}f(X,y)\big{]}=0$
for all $y\in\mathcal{Y}$, then we have that

$\mathbb{E}_{P_{X}}\big{[}\exp\big{(}\lambda
f(X,y)\big{)}\big{]}\leq\exp\left(\frac{\lambda^{2}\sigma^{2}}{2}\right),$

for all $y\in\mathcal{Y}$. Then, we can rearrange the terms and take the
expectation with respect to $P_{Y}$ to obtain

$\mathbb{E}_{P_{Y}\times P_{X}}\left[\exp\left(\lambda
f(X,Y)-\frac{\lambda^{2}\sigma^{2}}{2}\right)\right]\leq 1,$

which is the same expression we would obtain with the subgaussianity and zero-
mean conditions imposed in (ii). Now, let us consider the support of $P_{X,Y}$
to be $A=\textnormal{supp}(P_{X,Y})$. Then, it follows that

$\mathbb{E}_{P_{Y}\times P_{X}}\left[\chi_{A}\exp\left(\lambda
f(X,Y)-\frac{\lambda^{2}\sigma^{2}}{2}\right)\right]\leq 1,$

where $\chi_{A}$ is the characteristic function of the collection of sets $A$.
Finally, if we employ [10, Proposition 17.1] we have that

$\mathbb{E}_{P_{X,Y}}\left[\exp\left(\lambda
f(X,Y)-\frac{\lambda^{2}\sigma^{2}}{2}-\iota(X;Y)\right)\right]\leq 1.$

Now, we can insert the expectation over $P_{X,Y}$ inside the exponential by
means of Jensen’s inequality to obtain

$\exp\left(\lambda\,\mathbb{E}_{P_{X,Y}}[f(X,Y)]-\frac{\lambda^{2}\sigma^{2}}{2}-D_{\textnormal{KL}}(P_{X,Y}\>\|\>P_{Y}\times
P_{X})\right)\leq 1.$

Then, if we optimize for $\lambda$ and rearrange the terms we obtain that

$\big{|}\mathbb{E}_{P_{X,Y}}[f(X,Y)]\big{|}\leq\sqrt{2\sigma^{2}D_{\textnormal{KL}}(P_{X,Y}\>\|\>P_{Y}\times
P_{X})}.$

Finally, we apply [10, Corollary 3.1] to substitute $P_{Y}$ for any
distribution $Q_{Y}$ over $(\mathcal{Y},\mathscr{Y})$ and complete the proof.
∎

Note that we can apply Lemma 1 to a function
$f:\mathcal{X}\times(\mathcal{Y}\times\mathcal{Z})\rightarrow\mathbb{R}$ and
consider the random variables $X$, which is described by $P_{X}$ and is
independent of $Z$, and $Y|Z$, which is described by $P_{Y|Z}$. Then, if $f$
is either:

  1. (i)

zero-mean and $\sigma$-subgaussian under $P_{X}$ for all $y\in\mathcal{Y}$, or

  2. (ii)

zero-mean and $\sigma$-subgaussian under $P_{Y|Z}\times P_{X}$,

then, for all $\mathscr{Z}$-measurable distributions $Q_{Y|Z}$ over
$(\mathcal{Y},\mathscr{Y})$, we have that

$\big{|}\mathbb{E}_{P_{X,Y|Z}}[f(X,Y,Z)]\big{|}\leq\sqrt{2\sigma^{2}D_{\textnormal{KL}}(P_{X,Y|Z}\>\|\>Q_{Y|Z}\times
P_{X})}.$

###  -B Proof of Proposition 1

Consider the setting of Lemma 1 and let $X=Z_{i}$, $Y=W$, and
$f(X,Y)=\textnormal{gen}_{i}(W,Z_{i})\triangleq\mathbb{E}_{P_{Z}}[\ell(w,Z)]-\ell(w,Z_{i})$.
Then, since $\textnormal{gen}_{i}(W,Z_{i})$ is either (i) zero-mean and
$\sigma$-subgaussian under $P_{Z_{i}}$ for all $w\in\mathcal{W}$ or (ii) zero-
mean and $\sigma$-subgaussian under $P_{W}\times P_{Z_{i}}$, we have that

$\big{|}\mathbb{E}_{P_{W,Z_{i}}}\big{[}\textnormal{gen}_{i}(W,Z_{i})\big{]}\big{|}\leq\sqrt{2\sigma^{2}I(W;Z_{i})},$

where we let $Q_{Y}=P_{Y}=P_{W}$.

Finally, if we note that
$\mathbb{E}_{P_{W,S}}[\ell(W,Z_{i})]=\mathbb{E}_{P_{W,Z_{i}}}[\ell(W,Z_{i})]$
and we use the triangle inequality we get the desired result as follows:

$\displaystyle\big{|}\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\big{|}$
$\displaystyle\leq\left|\mathbb{E}_{P_{W}\times
P_{Z}}[\ell(W,Z)]-\mathbb{E}_{P_{W,S}}\left[\frac{1}{N}\sum_{i=1}^{N}\ell(W,Z_{i})\right]\right|$
$\displaystyle=\frac{1}{N}\left|\sum_{i=1}^{N}\big{(}\mathbb{E}_{P_{W}\times
P_{Z}}[\ell(W,Z)]-\mathbb{E}_{P_{W,Z_{i}}}[\ell(W,Z_{i})]\big{)}\right|$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left|\mathbb{E}_{P_{W,Z_{i}}}\big{[}\textnormal{gen}_{i}(W,Z_{i})\big{]}\right|$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\sqrt{2\sigma^{2}I(W;Z_{i})}.\qed$

###  -C Proof of Proposition 2

Consider the setting of Lemma 1 and, for a fixed $J$, let $X=S_{J}$,
$Y=(W|S_{J^{c}},R)$, and
$f(X,Y)=\textnormal{gen}_{J}(W,S_{J})\triangleq\mathbb{E}_{P_{Z}}[\ell(w,Z)]-\frac{1}{M}\sum_{i\in
J}\ell(w,Z_{i})$. Then, if (i) $\ell(w,Z)$ is $\sigma$-subgaussian under
$P_{Z}$ for all $w\in\mathcal{W}$, we have that
$\textnormal{gen}_{J}(W,S_{J})$ is zero-mean and $\sigma/\sqrt{M}$-subgaussian
under $P_{S_{J}}$; and if (ii) $\ell(W,Z)$ is $\sigma$-subgaussian under
$P_{W|S_{J^{c}},R}\times P_{Z}$, then $\textnormal{gen}_{J}(W,S_{J})$ is zero-
mean and $\sigma/\sqrt{M}$-subgaussian under $P_{W|S_{J^{c}},R}\times
P_{S_{J}}$. Therefore, we have that,

$\big{|}\mathbb{E}_{P_{W,S_{J}|S_{J^{c}},R}}\big{[}\textnormal{gen}_{J}(W,S_{J})\big{]}\big{|}\leq\sqrt{\frac{2\sigma^{2}}{M}D_{\textnormal{KL}}\big{(}P_{W,S_{J}|S_{J^{c}},R}\>\big{\|}\>Q_{W|S_{J^{c}},R}\times
P_{S_{J}}\big{)}},$ (12)

where $Q_{W|S_{J^{c}},R}$ is any
$(\mathscr{Z}^{\otimes(N-M)}\otimes\mathscr{R}\otimes\mathscr{J})$-measurable
distribution over $(\mathcal{W},\mathscr{W})$. Then, we may use Jensen’s
inequality to $|\mathbb{E}_{P_{W,S,R,J}}[\textnormal{gen}_{J}(W,S_{J})]|$ to
obtain that

$\big{|}\mathbb{E}_{P_{W,S,R,J}}\big{[}\textnormal{gen}_{J}(W,S_{J})\big{]}\big{|}\leq\mathbb{E}_{P_{J,S_{J^{c}},R}}\big{[}\big{|}\mathbb{E}_{P_{W,S_{J}|S_{J^{c}},R}}\big{[}\textnormal{gen}_{J}(W,S_{J})\big{]}\big{|}\big{]}.$
(13)

Finally, we may combine (12) and (13) with the fact that
$\mathbb{E}_{P_{W,S,R,J}}[\textnormal{gen}_{J}(W,S_{J})]=\mathbb{E}_{P_{W,S}}[\textnormal{gen}(W,S)]$
to obtain (3). ∎

###  -D Proof of Proposition 3

Consider the setting of Lemma 1 and let $X=U_{i}$,
$Y=(W,\tilde{Z}_{i},\tilde{Z}_{i+N})$, and
$f(X,Y)=\widehat{\textnormal{gen}}_{i}(W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i})\triangleq\ell\big{(}W,\tilde{Z}_{i+(1-U_{i})N}\big{)}-\ell\big{(}W,\tilde{Z}_{i+U_{i}N}\big{)}$.
Then, since $\ell(W,Z)$ is bounded in $[a,b]$, we also know that
$\widehat{\textnormal{gen}}_{i}(W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i})$ is
bounded in $[a-b,b-a]$, and thus it is $(b-a)$-subgaussian under any source of
randomness. Furthermore, since it has mean zero under $P_{U_{i}}$, we have
that

$\big{|}\mathbb{E}_{P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}}}}\big{[}\widehat{\textnormal{gen}}_{i}(W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i})\big{]}\big{|}\leq\sqrt{2(b-a)^{2}I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})},$

where we let
$Q_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N}}}=P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N}}}$.
Finally, if we note that
$\mathbb{E}_{P_{\smash{W,\tilde{S},U}}}\big{[}\widehat{\textnormal{gen}}(W,\tilde{S},U)\big{]}=\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}$,
that

$\mathbb{E}_{P_{\smash{W,\tilde{S},U}}}\big{[}\widehat{\textnormal{gen}}(W,\tilde{S},U)\big{]}=\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{P_{\smash{W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i}}}}\big{[}\widehat{\textnormal{gen}}_{i}(W,\tilde{Z}_{i},\tilde{Z}_{i+N},U_{i})\big{]},$

and we use the fact that $|\sum_{i=1}^{N}x_{i}|\leq\sum_{i=1}^{N}|x_{i}|$, we
obtain the result from (4). ∎

###  -E Proof of Proposition 4

Consider the setting of Lemma 1 and, for a fixed value of $J$, let $X=U_{J}$,
$Y=(W|\tilde{S},U_{J^{c}},R)$, and
$f(X,Y)=\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})\triangleq\frac{1}{M}\sum_{i\in
J}\ell\big{(}W,\tilde{Z}_{i+(1-U_{i})N}\big{)}-\ell\big{(}W,\tilde{Z}_{i+U_{i}N}\big{)}$.
Then, since $\ell(W,Z)$ is bounded in $[a,b]$, we also know that
$\ell\big{(}W,\tilde{Z}_{i+(1-U_{i})N}\big{)}-\ell\big{(}W,\tilde{Z}_{i+U_{i}N}\big{)}$
is bounded in $[a-b,b-a]$, and thus it is $(b-a)$-subgaussian under
$P_{U_{J}}$. Hence, since all the terms in the sum of
$\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})$ are
independent of each other under $P_{U_{J}}$, we know that
$\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})$ is
$(b-a)/\sqrt{M}$-subgaussian under $P_{U_{J}}$. Furthermore, since it has zero
mean under $P_{U_{J}}$, we have that

$\big{|}\mathbb{E}_{P_{\smash{W,U_{J}|\tilde{S},U_{J^{c}},R}}}\big{[}\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})\big{]}\big{|}\leq\sqrt{\frac{2(b-a)^{2}}{M}D_{\textnormal{KL}}\big{(}P_{\smash{W,U_{J}|U_{J^{c}},\tilde{S},R}}\>\big{\|}\>Q_{\smash{W|U_{J^{c}},\tilde{S},R}}\times
P_{U_{J}}\big{)}},$ (14)

where $Q_{\smash{W|U_{J^{c}},\tilde{S},R}}$ is any
$(\mathscr{U}^{\otimes(N-M)}\otimes\mathscr{Z}^{\otimes
2N}\otimes\mathscr{R}\otimes\mathscr{J})$-measurable distribution over
$(\mathcal{W},\mathscr{W})$. Then, we may use Jensen’s inequality to
$|\mathbb{E}_{P_{W,\tilde{S},U,R,J}}[\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})]|$
to obtain that

$\big{|}\mathbb{E}_{P_{W,\tilde{S},U,R,J}}\big{[}\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})\big{]}\big{|}\leq\mathbb{E}_{P_{\smash{J,\tilde{S},U_{J^{c}},R}}}\big{[}\big{|}\mathbb{E}_{P_{\smash{W,U_{J}|\tilde{S},U_{J^{c}},R}}}\big{[}\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})\big{]}\big{|}\big{]}.$
(15)

Finally, we may combine (14) and (15) with the fact that
$\mathbb{E}_{P_{\smash{W,\tilde{S},U,R,J}}}[\widehat{\textnormal{gen}}_{J}(W,U_{J},\tilde{S}_{J},\tilde{S}_{J+N})]=\mathbb{E}_{P_{W,S}}[\textnormal{gen}(W,S)]$
to obtain (5). ∎

###  -F Proof of Proposition 6

First of all, we note that

$D_{\textnormal{KL}}\big{(}P_{\smash{W|U,\tilde{S},V^{T}}}\>\big{\|}\>Q_{\smash{W|U_{J^{c}},\tilde{S},V^{T}}}\big{)}\leq\sum_{t=1}^{T}\mathbb{E}_{P_{\smash{W^{t-1}|U,\tilde{S},V^{t-1}}}}\big{[}D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)},$

since we first substitute $W_{T}$ by $W^{T}$ using the monotonicity of the
relative entropy, and then we employ the chain rule of the relative entropy
[10, Theorem 2.2] and the Markov properties of the problem. Note that we only
used the Markov property (with respect to the dependency with previous
hypotheses) of the problem for the distribution
$P_{\smash{W^{T}|U,\tilde{S},V^{T}}}$ and not for
$Q_{\smash{W^{T}|U_{J^{c}},\tilde{S},V^{T}}}$, since we will benefit from the
hypotheses’ trajectory when estimating $U_{J}$ with $\pi_{J,t}$. After that,
we note that at the iterations $t^{*}$ where the batch $V_{t^{*}}$ did not
include the sample $J$, the hypothesis $W_{{t^{*}}}$ is completely determined
by $W_{{t^{*}-1}},U_{J^{c}},\tilde{S},$ and $V^{t^{*}}$. Hence, as in [2], we
can drop these terms in the summation by considering
$Q_{\smash{W|W^{t^{*}-1},U_{J^{c}},\tilde{S},V^{t}}}=P_{\smash{W_{t}|W_{t^{*}-1},U_{J^{c}},\tilde{S},V^{t}}}$.
That is,

$\sum_{t=1}^{T}\mathbb{E}_{P_{\smash{W^{t-1}|U,\tilde{S},V^{t-1}}}}\big{[}D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}\big{]}\\\
=\sum\nolimits_{t\in\mathcal{T}_{J}(V^{T})}\mathbb{E}_{P_{\smash{W^{t-1}|U,\tilde{S},V^{t-1}}}}\big{[}D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}\big{]},$

where $\mathcal{T}_{J}(V^{T})$ is the set of iterations for which sample $J$
was included in the batches from $V^{T}$.

Then, we can evaluate the terms
$D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}$,
where similarly to [5], we note that
$P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}=\mathcal{N}(\mu_{J,t},\sigma_{t}I_{d})$,
where

$\mu_{J,t}=\theta_{t-1}-\frac{\eta_{t}}{|V_{t}|}\left((|V_{t}|-1)\nabla_{\theta_{t-1}}L_{S_{V_{t}\setminus
J}}(W_{\theta_{t-1}})+(1-U_{J})\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J})+U_{J}\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+N})\right).$

We may also define $Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}$ as a
Gaussian $\mathcal{N}(\mu^{\prime}_{J,t},\sigma_{t}I_{d})$, but since we do
not know $U_{J}$, we consider a weighted average of the gradients
$\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J})$ and
$\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+N})$ with an estimate
$\pi_{J,t}$ of the probability of $U_{J}=1$ based on $W^{t-1},\tilde{S}$,
$U_{J^{c}}$, and $V^{t}$. That is,

$\mu^{\prime}_{J,t}=\theta_{t-1}-\frac{\eta_{t}}{|V_{t}|}\left((|V_{t}|-1)\nabla_{\theta_{t-1}}L_{S_{V_{t}}\setminus
J}(W_{\theta_{t-1}})+(1-\pi_{J,t})\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J})+\pi_{J,t}\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+N})\right).$

Finally, similarly to [5], we can use the analytical expression of the
divergence between two Gaussians to obtain that

$D_{\textnormal{KL}}\big{(}\mathcal{N}(\mu_{J,t},\sigma_{t}I_{d})\>\big{\|}\>\mathcal{N}(\mu^{\prime}_{J,t},\sigma_{t}I_{d})\big{)}=(U_{J}-\pi_{J,t})^{2}\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma^{2}|V_{t}|^{2}},$

where
$\zeta_{J,t}\triangleq\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J})-\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+N})$
is the two-sample incoherence at iteration $t$. ∎

###  -G Proof of Proposition 7

The proof follows that of Proposition 6, except that we construct
$Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}$ as a mixture of two
Gaussians weighted by an estimate $\pi_{J,t}$ of the probability that
$U_{J}=1$. That is,
$(1-\pi_{J,t})\mathcal{N}(\mu^{0}_{J,t},\sigma_{t}I_{d})+\pi_{J,t}\mathcal{N}(\mu^{1}_{J,t},\sigma_{t}I_{d})$,
where

$\displaystyle\mu^{0}_{J,t}$
$\displaystyle=\theta_{t-1}-\frac{\eta_{t}}{|V_{t}|}\left((|V_{t}|-1)\nabla_{\theta_{t-1}}L_{S_{V_{t}}\setminus
J}(W_{\theta_{t-1}})+\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J})\right),$
$\displaystyle\mu^{1}_{J,t}$
$\displaystyle=\theta_{t-1}-\frac{\eta_{t}}{|V_{t}|}\left((|V_{t}|-1)\nabla_{\theta_{t-1}}L_{S_{V_{t}}\setminus
J}(W_{\theta_{t-1}})+\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+N})\right).$

Then, we apply [9, Lemma 2] to bound the relative entropy
$D_{\textnormal{KL}}\big{(}P_{\smash{W_{t}|W_{t-1},U,\tilde{S},V^{t}}}\>\big{\|}\>Q_{\smash{W|W^{t-1},U_{J^{c}},\tilde{S},V^{t}}}\big{)}$,
where we obtain that

$D_{\textnormal{KL}}\big{(}\mathcal{N}(\mu_{J,t},\sigma_{t}I_{d})\>\big{\|}\>(1-\pi_{J,t})\mathcal{N}(\mu^{0}_{J,t},\sigma_{t}I_{d})+\pi_{J,t}\mathcal{N}(\mu^{1}_{J,t},\sigma_{t}I_{d})\big{)}\\\
\leq-\log\left((1-\pi_{J,t})\exp\left(-U_{J}^{2}\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}\right)+\pi_{J,t}\exp\left(-(1-U_{J})^{2}\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}\right)\right).\qquad\qquad\qquad$
(16)

Finally, we can make (16) more compact by noting that the equation reduces to

$-\log\left((1-\pi_{J,t})+\pi_{J,t}\exp\left(-\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}\right)\right)$

when $U_{J}=0$, and to

$-\log\left((1-\pi_{J,t})\exp\left(-\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}\right)+\pi_{J,t}\right)$

when $U_{J}=1$. Hence, since $|U_{J}-\pi_{J,t}|$ is equal to $\pi_{J,t}$ when
$U_{J}=0$, and $(1-\pi_{J,t})$ when $U_{J}=1$, we may write the right hand
side of (16) as

$-\log\left(|U_{J}-\pi_{J,t}|\exp\left(-\frac{\eta_{t}^{2}\|\zeta_{J,t}\|^{2}}{2\sigma_{t}^{2}|V_{t}|^{2}}\right)+|1-U_{J}-\pi_{J,t}|\right),$

from which we obtain (10). ∎

###  -H Reduction of [3, Theorem 3.1]Negrea et al. [Theorem 3.1], under the
conditions of Corollary 1

If we consider $|J|=1$ and a bounded loss function
$\ell:\mathcal{W}\times\mathcal{Z}\rightarrow[a,b]$, we have that [3, Theorem
3.1] is

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\frac{(b-a)}{2\sqrt{2}}\,\mathbb{E}_{P^{\prime}_{1}}\left[\sqrt{\sum_{\smash{t=1}}^{T}\mathbb{E}_{{P^{\prime}_{2}}^{t}}\bigg{[}\frac{\eta_{t}^{2}}{\sigma_{t}^{2}}\|\xi_{t}\|^{2}\bigg{]}}\right],$

where $P^{\prime}_{1}=P_{J,S,V^{T}}$,
${P^{\prime}_{2}}^{t}=P_{W^{t-1}|S,V^{t-1}}$, and $\xi_{t}$ is defined as

$\xi_{t}\triangleq\frac{|V_{t}|-|S_{J^{c}}\cap
S_{V_{t}}|}{|V_{t}|}\left(\nabla_{\theta_{t-1}}L_{S_{1}}(W_{\theta_{t-1}})-\nabla_{\theta_{t-1}}L_{S_{2}}(W_{\theta_{t-1}})\right),$

where $S_{1}=S_{V_{t}}\setminus S_{J^{c}}$ and $S_{2}=S_{J^{c}}$. Note that if
the loss is $L$-Lipschitz and we fix $|V_{t}|=K$, we have that if $J\in V_{t}$
then $\|\xi_{t}\|=\frac{2L}{K}$ and otherwise $\|\xi_{t}\|=0$. Therefore, we
can eliminate from the summation all the iterations for which $J$ does not
belong to the batch $V_{t}$, which leaves us with

$\mathbb{E}_{P_{W,S}}\big{[}\textnormal{gen}(W,S)\big{]}\leq\frac{L(b-a)}{\sqrt{2}K}\,\mathbb{E}_{P_{\smash{J,V^{T}}}}\left[\sqrt{\sum_{\smash{t\in\mathcal{T}_{J}(V^{T})}}\frac{\eta_{t}^{2}}{\sigma_{t}^{2}}}\right].$

###  -I Derivation of the $U_{J}=1$U=1 estimate

Similarly to [5], we consider the estimation of $U_{J}=1$ with the knowledge
of $W^{t-1},U_{J^{c}},\tilde{S}$, and $V^{T}$. In order to do so, we consider
a function $\phi:\mathbb{R}\rightarrow[0,1]$ of the log-likelihood ratio of
the two hypotheses $\mathbb{H}_{1}\triangleq(U_{J}=1)$ and
$\mathbb{H}_{0}\triangleq(U_{J}=0)$. That is,

$\pi_{J,t}\triangleq\phi\left(\log\frac{P_{\smash{U_{J}|W^{t-1},\tilde{S},U_{J^{c}},V^{t-1}}}(1)}{P_{\smash{U_{J}|W^{t-1},\tilde{S},U_{J^{c}},V^{t-1}}}(0)}\right),$

where we use $V^{t-1}$ instead of $V^{T}$ in the probability distribution due
to the Markov properties of the problem.

Then, since the priors of $U_{J}$ are equal to $1/2$, i.e.,
$P_{U_{J}}(0)=P_{U_{J}}(1)=1/2$, the hypotheses $W_{t}$ are completely defined
by the parameters $\theta_{t}\in\mathbb{R}^{d}$, and given that the
stochasticity considered is Gaussian, we can assume that the probability
density functions $f(W^{t-1}|\tilde{S},U_{J}^{c},V^{t-1},U_{J}=u)$ exist and
that

$\phi\left(\log\frac{P_{\smash{U_{J}|W^{t-1},\tilde{S},U_{J^{c}},V^{t-1}}}(1)}{P_{\smash{U_{J}|W^{t-1},\tilde{S},U_{J^{c}},V^{t-1}}}(0)}\right)=\phi\left(\log\frac{f(W^{t-1}|\tilde{S},U_{J}^{c},V^{t-1},U_{J}=1)}{f(W^{t-1}|\tilde{S},U_{J}^{c},V^{t-1},U_{J}=0)}\right),$

where the density functions are

$\displaystyle f(W^{t-1}|$
$\displaystyle\tilde{S},U_{J}^{c},V^{t-1},U_{J}=u)=$
$\displaystyle\prod_{t=1}^{T}\left(\frac{1}{2\pi\sigma_{t}}\right)^{\frac{d}{2}}\exp\left(-\frac{1}{2\sigma_{t}^{2}}\left\|\theta_{t}-\theta_{t-1}+\eta_{t}\frac{|V_{t}|-1}{|V_{t}|}\nabla_{\theta_{t-1}}L_{V_{t}\setminus
J}(W_{\theta_{t-1}})+\frac{\eta_{t}}{|V_{t}|}\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+uN})\right\|^{2}\right).$

Therefore, the final estimation is

$\pi_{J,t}\triangleq\phi\left(\sum\nolimits_{t\in\mathcal{T}_{J}(V^{t})}(Y_{J,t,0}-Y_{J,t,1})\right),$

where

$Y_{J,t,u}=\frac{1}{2\sigma_{t}^{2}}\left\|\theta_{t}-\theta_{t-1}+\eta_{t}\frac{|V_{t}|-1}{|V_{t}|}\nabla_{\theta_{t-1}}L_{V_{t}\setminus
J}(W_{\theta_{t-1}})+\eta_{t}\frac{1}{|V_{t}|}\nabla_{\theta_{t-1}}\ell(W_{\theta_{t-1}},\tilde{Z}_{J+uN})\right\|^{2},$

and where the iterations $t^{*}$ where $J$ did not belong to $V_{t}$ are
dropped since $Y_{J,t^{*},0}=Y_{J,t^{*},1}$.

###  -J Comparison of mutual-information–based bounds on the randomized
subsample setting

It is known that in the standard setting, the expected generalization error
bounds are ordered, from tightest to loosest, as follows: [2, Proposition 1],
[7, Theorem 1], and [3, Theorem 2.4, after further applying Jensen’s
inequality]. This ordering follows from the fact that:

$\sum_{i=1}^{N}I(W;Z_{i})\leq
I(W;S)=\sum_{i=1}^{N}I(W;Z_{i}|S^{i-1})\leq\sum_{i=1}^{N}I(W;Z_{i}|S^{-i}),$

where $S^{-i}=S\setminus Z_{i}$ and $S^{i}=(S_{1},\ldots,S_{i})$. The proof
for the first inequality is presented in [2, Proposition 2] and the second
inequality can be derived similarly.

######  Lemma 2.

In the standard setting, we have that $I(W;Z_{i}|S^{i-1})\leq
I(W;Z_{i}|S^{-i})$ for all $i\in[N]$.

###### Proof.

If we exploit the fact that $Z_{i}$ are independent we have that:

$\displaystyle I(W;Z_{i}|S^{-i})$
$\displaystyle=I(W;Z_{i}|S^{-i})+I(Z_{i};S^{-i})$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{=}}I((W,S^{-i});Z_{i})$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}I(S^{i-1};Z_{i})+I(W;Z_{i}|S^{i-1})+I(S_{i+1}^{N};Z_{i}|W,S^{i-1})$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\geq}}I(W;Z_{i}|S^{i-1}),$

where for $i<j$ we have that $S_{i}^{j}=(Z_{i},\ldots,Z_{j})$ and for $i=j$ we
have that $S_{i}^{j}=Z_{i}$. Then, in (a) and (b) we used the chain rule of
the mutual information [10, Theorem 2.5] and in (c) the fact that the mutual
information is non-negative. ∎

We can use the same arguments in the bounds for the randomized subsample
setting, ordering them as follows: [5, Theorem 3.4, after further applying
Jensen’s inequality], [4, Theorem 5.1], and [5, Theorem 3.7, after further
applying Jensen’s inequality]. This ordering, as before, follows since

$\sum_{i=1}^{N}I(W;U_{i}|\tilde{S})\leq
I(W;U|\tilde{S})=\sum_{i=1}^{N}I(W;U_{i}|\tilde{S},U^{i-1})\leq\sum_{i=1}^{N}I(W;U_{i}|\tilde{S},U^{-i}),$

where $U^{-i}=U\setminus U_{i}$ and $U^{i}=(U_{1},\ldots,U_{i})$. Nonetheless,
the bound obtained in Proposition 3 is the tightest, when the bounds are
written in their mutual information form after applying Jensen’s inequality,
as dictated by the following lemma.

######  Lemma 3.

In the randomized subsample setting, we have that
$I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})\leq I(W;U_{i}|\tilde{S})$ for all
$i\in[N]$.

###### Proof.

We may start the proof by noting that

$I(W;U_{i}|\tilde{S})=I(U_{i};(W,\tilde{S}))-I(U_{i},\tilde{S})=I(U_{i};(W,\tilde{S})),$
(17)

where we used the small chain rule of the mutual information [10, Theorem 2.5]
and the fact that $U$ and $\tilde{S}$ are independent. Similarly, we have that

$I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})=I(U_{i};(W,\tilde{Z}_{i},\tilde{Z}_{i+N})).$
(18)

Then, we may operate with $I(W;U_{i}|\tilde{S})$ in the form of (17) to obtain
that it is greater or equal than $I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})$ in
the form of (18), namely

$\displaystyle I(U_{i};(W,\tilde{S}))$
$\displaystyle=I(U_{i};(W,\tilde{Z}_{i},\tilde{Z}_{i+N},\tilde{S}^{-i})$
$\displaystyle=I(U_{i};(W,\tilde{Z}_{i},\tilde{Z}_{i+N}))+I(U_{i};\tilde{S}^{-i}|W,\tilde{Z}_{i},\tilde{Z}_{i+N})$
$\displaystyle\geq I(U_{i};(W,\tilde{Z}_{i},\tilde{Z}_{i+N})),$

where $\tilde{S}^{-i}=\tilde{S}\setminus(\tilde{Z}_{i},\tilde{Z}_{i+N})$ and
we used again the small chain rule of mutual information and the fact that the
mutual information is non-negative. ∎

This way, we have that

$\sum_{i=1}^{N}I(W;U_{i}|\tilde{Z}_{i},\tilde{Z}_{i+N})\leq\sum_{i=1}^{N}I(W;U_{i}|\tilde{S})\leq
I(W;U|\tilde{S})=\sum_{i=1}^{N}I(W;U_{i}|\tilde{S},U^{i-1})\leq\sum_{i=1}^{N}I(W;U_{i}|\tilde{S},U^{-i}).$