# Anomalous Relativistic Emission from Self-Modulated Plasma Mirrors

M. Lamač  ELI Beamlines Facility, The Extreme Light Infrastructure ERIC, Za
Radnicí 835, Dolní Břežany, 25241, Czechia  Faculty of Mathematics and
Physics, Charles University, Ke Karlovu 3, Prague 2, 12116, Czechia  K. Mima
Institute of Laser Engineering, Osaka University, 2-6 Yamadaoka, Suita, Osaka
565-0871, Japan  J. Nejdl  ELI Beamlines Facility, The Extreme Light
Infrastructure ERIC, Za Radnicí 835, Dolní Břežany, 25241, Czechia  Faculty of
Nuclear Science and Physical Engineering, Czech Technical University in
Prague, Břehová 7, Prague 1, 11519, Czechia  U. Chaulagain  ELI Beamlines
Facility, The Extreme Light Infrastructure ERIC, Za Radnicí 835, Dolní
Břežany, 25241, Czechia  S. V. Bulanov  ELI Beamlines Facility, The Extreme
Light Infrastructure ERIC, Za Radnicí 835, Dolní Břežany, 25241, Czechia
Kansai Photon Science Institute, National Institutes for Quantum and
Radiological Science and Technology, 8-1-7 Umemidai, Kizugawa, 619-0215,
Kyoto, Japan

###### Abstract

The interaction of intense laser pulses with plasma mirrors has demonstrated
the ability to generate high-order harmonics, producing a bright source of
extreme ultraviolet (XUV) radiation and attosecond pulses. Here, we report an
unexpected transition in this process.  We show that the loss of spatio-
temporal coherence in the reflected high-harmonics can lead to a new regime of
highly-efficient coherent XUV generation, with an extraordinary property where
the radiation is directionally anomalous, propagating parallel to the mirror
surface. With analytical calculations and numerical particle-in-cell
simulations, we discover that the  radiation emission is due to laser-driven
oscillations of relativistic electron nanobunches which originate from a
plasma surface instability.

††preprint: APS/123-QED Figure 1: Principle of RIME.

Generation of attosecond pulses and extreme ultraviolet radiation (XUV)
originating from the interaction of a relativistically intense laser with a
plasma mirror has now been investigated for almost three decades [1, 2, 3, 4,
5]. With experimental results supporting its potential for applications in
fundamental science, ultrafast science, attosecond interferometry or imaging
[2, 6, 7, 8, 9, 10, 11, 12], this mechanism presents a competitive alternative
to the contemporary workhorse of attosecond science, which is high-harmonic
generation (HHG) from noble gases originating from non-linear laser-atom
interactions [13, 11, 14, 15]. The potential of relativistic high-harmonic
generation reveals itself in the lack of ionization thresholds, which pose a
hard limit on intensity of conventional gas or sollid HHG sources. With the
growing availibility of commercial high-repetition rate laser systems with
peak powers in the terawatt range, relativistic generation of broadband,
bright and ultrashort radiation will be attractive even at small university-
scale laboratories. The emission of relativistic high harmonics originates
from plasma surface electrons performing non-linear oscillations within the
laser field, with velocity close to the speed of light. This occurs when the
amplitude of the incident laser exceeds the threshold amplitude of
relativistic optics [16], which is characterized in terms of the normalized
laser amplitude as $a_{0}=eE_{0}/m_{e}\omega_{0}c\geq 1$, where $e$ is the
elementary charge, $m_{e}$ the electron mass, $c$ the speed of light,
$\omega_{0}$ is the angular frequency of the laser and $E_{0}$ the amplitude
of the laser electric field. The coherent reflection from the plasma surface
can be additionally affected for very high laser intensities such that the
ions can accelerate to a fraction of the speed of light in a single laser
cycle, $a_{0}\geq(m_{i}/Zm_{e})^{1/2}$ [17, 18], where $m_{i}$ is the ion mass
and $Z$ is the ion charge number.

In this letter, we report the discovery of a new  regime of XUV light
generation, which we call relativistic instability-modulated emission (RIME),
originating from the interaction of an intense laser pulse with a plasma
mirror, which is self-modulating due to unstable return current induced by the
collisionless absorption of the laser. RIME generates broadband XUV radiation
with high-efficiency and an anomalous propagation characteristic, where the
radiation is emitted parallel to the plasma mirror surface. The mechanism of
RIME is illustrated in Fig. 1. An intense P-polarized laser pulse is obliquely
incident on the surface of a relativistically overdense plasma mirror, $1\leq
a_{0}<n_{e}/n_{c}$, where $n_{e}$ is the electron plasma density,
$n_{c}=m_{e}\epsilon_{0}\omega_{0}^{2}/e^{2}$ is the critical plasma density
and $\epsilon_{0}$ is the vacuum permittivity. At the beginning of
interaction, the intense incident laser coherently reflects from and
accelerates the surface electrons into the plasma bulk (Fig. 1b) by the Brunel
effect [19, 20]. These bulk-penetrating Brunel electrons induce neutrality-
restoring return currents flowing along the mirror periphery, consisting of
counter-streaming electrons and ions which generate intense quasi-static
magnetic field on the mirror surface [21]. The electron-ion two-stream grows
unstable with a growth rate $\Gamma\propto\omega_{pe}(Zm_{e}/m_{i})^{1/3}$
[22], which is of the order of the laser frequency for solid high-Z targets
with electron plasma densities $n_{e}/n_{c}\geq(m_{i}/Zm_{e})^{2/3}$.
Therefore, after laser-plasma interaction time of $\approx 1/\Gamma$, the
plasma mirror self-modulates with wavelength of the order of the plasma
wavelength $\lambda_{p}=2\pi c/\omega_{pe}$, where
$\omega_{pe}=\left(e^{2}n_{e}/m_{e}\epsilon_{0}\right)^{1/2}$ is the electron
plasma frequency. As the plasma wave grows, the oscillating electrons are
bunched and the individual bunch emissions are coherently-enhanced while the
reflected wave loses its spatio-temporal coherence (Fig. 1c). As the laser
amplitude ramps up in the interaction region, the unstable plasma wave grows
non-linear and breaks [23], releasing electron nanobunches to be accelerated
by the laser across the magnetized plasma surface to velocities close to the
speed of light, resulting in surface-parallel relativistic beaming of
individual bunch emissions (Fig. 1d).

The coherent intensity spectrum of RIME generated over a half-oscillation
period by an electron bunch containing $N_{e}$ electrons can be obtained as
(See Supplementary Material [24] for derivation details)

$I(\omega)=N_{e}^{2}\frac{\sqrt{3}e^{2}\gamma}{4\pi\epsilon_{0}c}\frac{\omega/\omega_{c}}{\left(1+(\omega/\omega_{b})^{2}\right)^{2}}\int_{\omega/\omega_{c}}^{\infty}K_{5/3}(\xi)\hskip
1.42262pt\text{d}\xi,$ (1)

where $K_{5/3}(x)$ is the modified Bessel function,
$\omega_{c}=3c\gamma^{3}/2\lambda_{0}$ is the critical frequency indicating an
exponential cut-off in the spectrum, $\lambda_{0}$ is the laser wavelength and
$\gamma$ is the electron Lorentz factor. The electron bunch modulation
frequency is given as $\omega_{b}=c/L_{b}$, where $L_{b}$ is the electron
bunch length. Bunch modulation frequency indicates a transition in the
radiation spectrum, from the coherent regime of radiation emission, where
$I\propto N_{e}^{2}$ for frequencies smaller than or of the same order
$\omega\lesssim\omega_{b}$, into the regime of incoherent emission, where
$I\propto N_{e}$ for $\omega\gg\omega_{b}$.

Figure 2: PIC simulation of the surface instability. a) Time evolution of the
longitudinal component of the ion current, shown up to $t=80$ fs. Dashed line
following linear phase velocity of the surface wave corresponds to
$v_{p}/c=0.01$. b) Time evolution of $|j_{i,\parallel}|$ averaged over
$r_{\parallel}\in[-1\ \mu\mathrm{m},1\ \mu\mathrm{m}]$ (black) and
corresponding instantaneous growth rate $\Gamma(t)$ (blue). c) Fourier
transform of the ion current in the linear phase of the instability, $0\text{
fs}<t<55\text{ fs}$ (coloured, smoothened) and the real part of the solution
of Eq. 2 (black, dashed) calculated for the electron drift velocity
$v_{de}/c=0.01,\ \omega_{p}/\omega_{0}=31.6$. Figure 3: PIC simulation of
RIME. Average kinetic energy of electrons (a) and the longitudinal electron
current (b) at the time of instability saturation, $t=55$ fs. Transverse (c)
and longitudinal (d) electron current, and electric (e) and magnetic field (f)
components at the time of peak laser amplitude arrival, $t=80$ fs.

To describe the modulation frequency of the electron bunch, we must consider
the origin of the bunch modulating instability. Fast Brunel electrons
penetrate into the plasma mirror and induce a return current composed of
counter-streaming electrons and ions flowing along the surface. Assuming that
the drift velocity of the return electrons is much larger than ions $v_{de}\gg
v_{di}$, the ion velocity may be neglected and, following the usual treatment
of two-stream instability, we obtain the well-known Buneman instability (BI)
dispersion relation for a small perturbation [22],

$\frac{\omega_{pe}^{2}}{(\omega-
kv_{de})^{2}}+\frac{\omega_{pi}^{2}}{\omega^{2}}=1,$ (2)

where $\omega_{pi}=\left(Z^{2}e^{2}n_{i}/m_{i}\epsilon_{0}\right)^{1/2}$ is
the ion plasma frequency. For an unstable growing mode, the mirror surface,
and therefore the Brunel electrons, will be modulated according to the
instability wavelength as illustrated in Fig. 1c. Solving Eq. 2 for the
complex frequency $\omega\rightarrow\omega+i\Gamma$, we obtain from the
imaginary part the maximum growth rate of the Buneman instability as

$\Gamma_{m}=\omega_{pe}\frac{\sqrt{3}}{2}\left(\frac{Z^{2}m_{e}}{2m_{i}}\right)^{1/3},$
(3)

which is approximately valid for all modes in the band
$|kv_{de}-\omega_{p}|\lesssim(3/2)(\omega_{pe}\omega_{pi}^{2})^{1/3}$ [22].
The condition for RIME to occur therefore requires laser pulse duration to be
larger than $\approx 1/\Gamma_{m}$. This straightforward result allows us to
see that the plasma surface instability e-folding time can be of the order of
a single laser cycle, since $\Gamma_{m}\approx\omega_{0}$ for solid density
plasma, $n_{e}\approx 10^{3}n_{c}$, which means that the plasma surface
instability can fully manifest already within a few laser cycles.

To study the process in detail, we have performed multi-dimensional particle-
in-cell (PIC) simulations (See Supplementary Material [24] for simulation
details). A P-polarized laser pulse defined with pulse duration
$\tau_{fwhm}=30$ fs, laser wavelength $\lambda_{0}=1\text{ }\mu$m and peak
intensity $I_{0}=10^{22}\text{ W/cm}^{2}$ corresponding to a normalized laser
amplitude $a_{0}=85.5$, was focused with an incidence angle
$\theta=45^{\circ}$ to a spot size with waist radius $w_{0}=2\text{ }\mu$m
upon a plasma mirror composed of uniformly overlapping electrons and ions with
matching density $n_{i}/n_{c}=n_{e}/n_{c}=1000$ and temperature
$k_{B}T=100\text{ eV}$. Figure 2 shows the analysis of plasma surface
instability observed in the PIC simulation. Fig. 2a shows the temporal
evolution of the surface-parallel ion current, revealing an unstable plasma
wave propagating in the direction of electron return flow with phase velocity
$v_{p}/c\approx 0.01$. This corresponds to the drift velocity of the electron
return current, since from the current neutrality condition $v_{de}/c\approx
a_{0}n_{c}/n_{e}\approx 0.01$ at $t\approx 45$ fs when the amplitude of the
incident laser is $a_{0}\approx 10$. Fig. 2b presents the time evolution of
the instability, showing the instability saturation and clear separation
between the linear and non-linear phases occuring at $t\approx 55$ fs. We note
that the maximum instantaneous growth rate matches the prediction given by Eq.
3. Fig. 2c shows the numerical dispersion of the instability overlaid with the
real part of the solution of Eq. 2, showing a match between the PIC and
Buneman unstable modes.

Figure 3 presents a detailed view of the RIME origin. In Fig. 3a, Brunel
electrons can be seen penetrating into the bulk in the direction of laser
propagation at twice the laser frequency, which is due to the relativistic
$\mathbf{j}\times\mathbf{B}$ Lorentz force term. This leads to the growth of
unstable return current flowing along the periphery seen in Fig. 3b. As the
unstable plasma wave breaks, oscillating electron nanobunches are accelerated
by the laser across the surface within the focal region to relativistic
velocities. This is shown with the electron current components in Figs. 3c, d.
The transverse component highlights the transverse oscillatory turning points
of the individual nanobunches occuring at $j_{\perp,e}=0$. On the other hand,
it is at these points where longitudinal velocity is largest,
$v_{\parallel}\approx c$, which leads to relativistic beaming of radiation
along the surface (See Supplementary Material [24] for a movie of the
process). This results in the loss of reflected wave coherence and the
emergence of RIME XUV bursts seen in the perpendicular component of the
magnetic field $B_{z}$ shown in Fig. 3f. Additionally, the magnetic field
reveals that the instability region is extremely magnetized due to the return
current, with amplitude of the order of the incident laser. This leads to
enhanced confinement of relativistic electrons towards the plasma surface
[21]. The electric field component $E_{y}$ in Fig. 3e shows the incident
P-polarized laser interfering with the intense RIME bursts.

Figure 4: Radiation properties of RIME. a) Intensity spectra with the
analytical model given by Eq. 1. b) Intensity spectra for S and P laser
polarizations. c) Instantaneous power of radiation emitted along the surface
calculated for two electron bunches oscillating above the surface
($r_{\perp}=0$) with $\gamma\approx a_{0}$. d) Laser-to-XUV energy conversion
efficiency dependence on pre-plasma scale length $L$. e) Spatial distribution
of XUV intensity for the ROM-optimal and f) the RIME-optimal pre-plasma.

Radiation characteristics of RIME are presented in Fig. 4. Trajectories of two
characteristic electron bunches with $\gamma\approx a_{0}$ are presented in
Fig. 4c. Calculated radiation power confirms multiple bursts emitted along the
bunch trajectory. The intensity spectra of RIME and the wave reflected due to
the relativistic oscillations of the mirror (ROM) are shown in Fig. 4a. The
spatio-temporal coherence of the reflected wave is reduced with the onset of
RIME, leading to larger XUV conversion efficiency for the emission along the
mirror surface. To evaluate coherent enhancement of radiation due to electron
bunching, we have performed another PIC simulation with immobile ions. The
simulation confirmed that in this case BI and RIME are not present. In this
scenario, the coherence of high harmonics composing the reflected wave is
significantly improved, as shown in Fig. 4a. However, compared to the RIME
spectrum, the efficiency significantly drops for $\omega/\omega_{0}>10$, which
can be explained by the nanobunching effect occuring in the realistic
simulation, since the individual bunch sizes can be smaller than
$\lambda_{pe}=\lambda_{0}/31.6\approx 31\text{ nm}$ as shown in Fig. 3c, d.
The continuous RIME spectrum is explained by the fact that the peak laser-
plasma interaction, and therefore strongest emission, occurs deep into the
non-linear phase of the instability evolution at $t=80$ fs, as seen in Fig.
2b. This leads to non-periodic trains of electron nanobunches individually
producing broadband XUV bursts that add up to a broad, continuous spectrum. We
point out that the bunching effect also enhances the low-order harmonics
composing the reflected wave, which can be seen when comparing the two ROM
spectra shown in Fig. 4a. This is because the distances between the individual
bunches within a single laser oscillation are smaller than the wavelengths of
the low-order harmonics, which can be seen in Figs. 3e, f. To compare the RIME
spectrum with the analytical result given by Eq. 1, we proceed to estimate the
bunch modulation frequency. The average value of electron drift velocity
inside the return current observed in the PIC simulation is $v_{de}/c\approx
0.18$ at the peak interaction time $t=80$ fs (Fig. 3d). The bunch modulation
frequency due to BI can be therefore estimated as $\omega_{b}=c/L_{b}\approx
2c/\lambda_{B}\approx(c\omega_{p}/v_{de}\pi)\approx 18\omega_{0}$,
corresponding to an electron bunch length of $L_{b}\approx 88\text{ nm}$ and
instability wavelength $\lambda_{B}\approx 0.18\text{ }\mu\text{m}$, which is
in agreement with the features seen in Fig. 3c, d. Considering such modulation
frequency, RIME spectrum as given by Eq. 1, with energy of laser-accelerated
electrons given $\gamma\approx a_{0}=85.5$, is presented in Fig. 4a, showing
an excellent agreement with the PIC result. In Fig. 4b we show the dependence
of emitted radiation on laser polarization. When the incident laser is
S-polarized, BI and RIME are not present and only ROM-reflected wave remains
with less efficient high-harmonic generation, which confirms a well-known
property of ROM [2].

Previous studies have demonstrated that the presence of pre-plasma with scale
length satisfying $kL\approx 1$ can optimize ROM conversion efficiency [25,
26], where $k=\omega_{0}/c$ is the laser wave number number and $L$ is the
pre-plasma scale length. This optimum comes from the balance of the strong
electrostatic field due to the space-charge distribution limiting electron
oscillations when $kL<1$, and the growth of plasma waves leading to reflected
wave coherence loss when $kL>1$ [27, 20]. In the case when $kL>1$, the plasma
wave growth is resonant for a P-polarized laser incident upon inhomogeneous
plasma with a scale length satisfying [28, 27]

$(kL)^{1/3}\sin\theta\approx 0.8,$ (4)

where $\theta$ is the laser incidence angle. To investigate the effect of non-
zero pre-plasma scale lengths on RIME, we have conducted PIC simulations in
the range $0\leq kL\leq\pi$. The results are summarized in Fig. 4d, where we
show the conversion efficiency of laser energy to XUV wavelengths $\lambda\leq
100$ nm. Our numerical results match the experimentally discovered ROM optimum
found in [25, 26], which occurs when $kL\approx 1$. For such scale length, the
total reflectivity reaches up to $60\%$, with around $0.4\%$ of laser energy
converted to XUV. The results for RIME show high XUV efficiency, but more
intricate dependence. First, as discussed above, the coherent enhancement due
to nanobunching yields larger XUV conversion efficiency by up to an order-of-
magnitude. Second, the XUV yields are anti-correlated. This is due to the fact
that the coherent enhancement of RIME results in the loss of coherence in the
reflected wave and vice versa. Finally, the RIME XUV yield reveals an optimal
scale length for the simulation with $L/\lambda_{0}=0.25$, where XUV
conversion efficiency grows up to $2\%$. To compare to conventional XUV
sources, the widely-used gas HHG source operates at XUV energy conversion
efficiency of $\approx 10^{-5}$ [14, 15], with maximum incident laser
intensity limited to $\sim 10^{15}\text{ W.cm}^{-2}$.

Figure 5: a) Temporal profile of XUV radiation for the case of RIME (black)
and ROM (red) optimal scale length, offset for clarity. b) Angular
distribution of spectral intensity for ROM-optimal scale length
$L/\lambda_{0}=0.1$. Colormap is saturated for higher contrast in the XUV
region.

For the simulated incidence angle of $45^{\circ}$, the condition for resonant
plasma wave growth given by Eq. 4 gives the scale length as
$L/\lambda_{0}=0.23$, an excellent match which shows that the origin of the
RIME optimum is due to the resonant growth of large-amplitude plasma waves
which facilitate faster wave-breaking of instability-modulated electrons into
the laser field. The XUV intensity distribution for the two optimal cases are
shown in Figs. 4e, f. In the case of $kL\approx 1$, the laser is initially
reflected coherently by ROM. As the unstable plasma wave saturates, the
spatio-temporal XUV coherence is reduced and coherent XUV bursts propagating
along the mirror surface emerge. In the case of resonant plasma wave growth,
$(kL)^{1/3}\sin\theta\approx 0.8$, the reflected wave loses its spatio-
temporal coherence almost immediatelly and most of the XUV radiation is
increasingly collimated towards the surface as the laser intensity ramps up.

The angular distribution of RIME is given by the emission angle of laser-
accelerated relativistic electrons given by $\tan\theta=(2/(\gamma-1))^{1/2}$
[20] . For the electrons oscillating in the peak laser amplitude
$\gamma\approx a_{0}$, the emission angle is therefore $\theta\approx
8.7^{\circ}=150$ mrad, which is in reasonable agreement with the XUV intensity
distributions shown in Figs. 4e, f, and the angular distribution of RIME for
the case of $kL\approx 1$ shown in Fig. 5b. The angular distribution shows
clear separation between the high-frequency radiation emitted by ROM and RIME,
which is also visible in the corresponding XUV intensity distribution shown in
Fig. 4e. The temporal profile of XUV radiation for the two optimal cases is
shown in Fig. 5a. In correspondence with Fig. 4e, the radiation pulse of the
ROM-optimal case $L/\lambda_{0}=0.1$ shows initially coherent and smooth
reflected wave profile at $t<55$ fs, losing its coherence at $t=55$ fs, and
then transitioning to the RIME profile modulated by coherent attosecond bursts
at $t>55$ fs. The case of RIME-optimal scale length $L/\lambda_{0}=0.25$ shows
that alredy at the beginning of interaction, $t<55$ fs, the XUV pulse is
modulated with the RIME bursts in accordance with Fig. 4f. As the laser peak
arrives at $t=80$ fs, coherently-enhanced giant attosecond XUV pulses emerge
due to the strong electron nanobunching from the resonant plasma wave growth.

In conclusion, a new high-yield mechanism of coherent XUV light generation
called RIME was discovered to occur during the interaction of relativistically
intense P-polarized laser pulse with overdense plasma satisfying $1\leq
a_{0}<n_{e}/n_{c}$. The radiation emission is directionally anomalous,
propagating parallel to the mirror surface. With numerical and analytical
methods, we have found that RIME occurs due to laser-driven oscillations of
electron nanobunches which emerge from a return current instability induced by
collisionless absorption of the incident laser. Furthermore, by varying the
pre-plasma scale length, we have found that RIME is anti-correlated with the
reflected high-harmonics, showing the possibility to tune between two
directionally-separated XUV radiation sources in a single experimental
configuration. Finally, we have found an optimal pre-plasma scale length for
RIME corresponding to resonant growth of plasma waves at the mirror surface.
The optimal XUV conversion efficiency of RIME reaches percent-level,
presenting a new approach for future experiments aiming to produce high-yield
coherent XUV radiation.

## Acknowledgements

This work was supported by the project ADONIS
(CZ.02.1.01/0.0/0.0/16_019/0000789).

## References

  * Mori  _et al._ [1993] W. Mori, C. Decker, and W. Leemans, Relativistic harmonic content of nonlinear electromagnetic waves in underdense plasmas, IEEE transactions on plasma science 21, 110 (1993).
  * Teubner and Gibbon [2009] U. Teubner and P. Gibbon, High-order harmonics from laser-irradiated plasma surfaces, Reviews of Modern Physics 81, 445 (2009).
  * Bulanov  _et al._ [1994] S. V. Bulanov, N. Naumova, and F. Pegoraro, Interaction of an ultrashort, relativistically strong laser pulse with an overdense plasma, Physics of Plasmas 1, 745 (1994).
  * Vincenti  _et al._ [2014] H. Vincenti, S. Monchocé, S. Kahaly, G. Bonnaud, P. Martin, and F. Quéré, Optical properties of relativistic plasma mirrors, Nature communications 5, 3403 (2014).
  * Pirozhkov  _et al._ [2012] A. Pirozhkov, M. Kando, T. Z. Esirkepov, P. Gallegos, H. Ahmed, E. Ragozin, A. Y. Faenov, T. Pikuz, T. Kawachi, A. Sagisaka, _et al._ , Soft-x-ray harmonic comb from relativistic electron spikes, Physical Review Letters 108, 135004 (2012).
  * Dromey  _et al._ [2009] B. Dromey, D. Adams, R. Hörlein, Y. Nomura, S. Rykovanov, D. Carroll, P. Foster, S. Kar, K. Markey, P. McKenna, _et al._ , Diffraction-limited performance and focusing of high harmonics from relativistic plasmas, Nature Physics 5, 146 (2009).
  * Yeung  _et al._ [2014] M. Yeung, B. Dromey, S. Cousens, T. Dzelzainis, D. Kiefer, J. Schreiber, J. Bin, W. Ma, C. Kreuzer, J. Meyer-ter Vehn, _et al._ , Dependence of laser-driven coherent synchrotron emission efficiency on pulse ellipticity and implications for polarization gating, Physical Review Letters 112, 123902 (2014).
  * Heissler  _et al._ [2012] P. Heissler, R. Hörlein, J. M. Mikhailova, L. Waldecker, P. Tzallas, A. Buck, K. Schmid, C. Sears, F. Krausz, L. Veisz, _et al._ , Few-cycle driven relativistically oscillating plasma mirrors: a source of intense isolated attosecond pulses, Physical Review Letters 108, 235003 (2012).
  * Naumova  _et al._ [2004] N. Naumova, J. Nees, I. Sokolov, B. Hou, and G. Mourou, Relativistic generation of isolated attosecond pulses in a $\lambda$ 3 focal volume, Physical Review Letters 92, 063902 (2004).
  * Wheeler  _et al._ [2012] J. A. Wheeler, A. Borot, S. Monchocé, H. Vincenti, A. Ricci, A. Malvache, R. Lopez-Martens, and F. Quéré, Attosecond lighthouses from plasma mirrors, Nature Photonics 6, 829 (2012).
  * Smirnova  _et al._ [2009] O. Smirnova, Y. Mairesse, S. Patchkovskii, N. Dudovich, D. Villeneuve, P. Corkum, and M. Y. Ivanov, High harmonic interferometry of multi-electron dynamics in molecules, Nature 460, 972 (2009).
  * Neutze  _et al._ [2000] R. Neutze, R. Wouts, D. Van der Spoel, E. Weckert, and J. Hajdu, Potential for biomolecular imaging with femtosecond x-ray pulses, Nature 406, 752 (2000).
  * Krausz and Ivanov [2009] F. Krausz and M. Ivanov, Attosecond physics, Reviews of modern physics 81, 163 (2009).
  * Nefedova  _et al._ [2017] V. Nefedova, M. Albrecht, M. Kozlová, and J. Nejdl, Development of a high-flux xuv source based on high-order harmonic generation, Journal of Electron Spectroscopy and Related Phenomena 220, 9 (2017).
  * Heyl  _et al._ [2016] C. M. Heyl, H. Coudert-Alteirac, M. Miranda, M. Louisy, K. Kovács, V. Tosa, E. Balogh, K. Varjú, A. L’Huillier, A. Couairon, _et al._ , Scale-invariant nonlinear optics in gases, Optica 3, 75 (2016).
  * Mourou  _et al._ [2006] G. A. Mourou, T. Tajima, and S. V. Bulanov, Optics in the relativistic regime, Reviews of modern physics 78, 309 (2006).
  * Macchi  _et al._ [2005] A. Macchi, F. Cattani, T. V. Liseykina, and F. Cornolti, Laser acceleration of ion bunches at the front surface of overdense plasmas, Physical review letters 94, 165003 (2005).
  * Esirkepov  _et al._ [1999] T. Z. Esirkepov, Y. Sentoku, K. Mima, K. Nishihara, F. Califano, F. Pegoraro, N. Naumova, S. Bulanov, Y. Ueshima, T. Liseikina, _et al._ , Ion acceleration by superintense laser pulses in plasmas, Journal of Experimental and Theoretical Physics Letters 70, 82 (1999).
  * Brunel [1987] F. Brunel, Not-so-resonant, resonant absorption, Physical Review Letters 59, 52 (1987).
  * Gibbon [2005] P. Gibbon,  _Short pulse laser interactions with matter: an introduction_ (World Scientific, 2005).
  * Nakamura  _et al._ [2004] T. Nakamura, S. Kato, H. Nagatomo, and K. Mima, Surface-magnetic-field and fast-electron current-layer formation by ultraintense laser irradiation, Physical review letters 93, 265002 (2004).
  * Buneman [1959] O. Buneman, Dissipation of currents in ionized media, Physical Review 115, 503 (1959).
  * Bulanov and Sasorov [1978] S. Bulanov and P. Sasorov, Tearing of a current sheet and reconnection of magnetic lines of force, Soviet Journal of Plasma Physics 4, 418 (1978).
  * [24] See Supplemental material for more details.
  * Kahaly  _et al._ [2013] S. Kahaly, S. Monchocé, H. Vincenti, T. Dzelzainis, B. Dromey, M. Zepf, P. Martin, and F. Quéré, Direct observation of density-gradient effects in harmonic generation from plasma mirrors, Physical review letters 110, 175001 (2013).
  * Dollar  _et al._ [2013] F. Dollar, P. Cummings, V. Chvykov, L. Willingale, M. Vargas, V. Yanovsky, C. Zulick, A. Maksimchuk, A. Thomas, and K. Krushelnick, Scaling high-order harmonic generation from laser-solid interactions to ultrahigh intensity, Physical Review Letters 110, 175002 (2013).
  * Ginzburg [1964] V. L. Ginzburg,  _The Propagation of Electromagnetic Waves in Plasma_ (Pergamon, 1964).
  * Denisov [1957] N. G. Denisov, On a singularity of the field of an electromagnetic wave propagated in an inhomogeneous plasma, Sov. Phys. - JETP 4 4, 544 (1957).
  * Arber  _et al._ [2015] T. Arber, K. Bennett, C. Brady, A. Lawrence-Douglas, M. Ramsay, N. Sircombe, P. Gillies, R. Evans, H. Schmitz, A. Bell, _et al._ , Contemporary particle-in-cell approach to laser-plasma modelling, Plasma Physics and Controlled Fusion 57, 113001 (2015).
  * Jackson [1999] J. D. Jackson,  _Classical electrodynamics_ (John Wiley & Sons, 1999).
  * Hirschmugl  _et al._ [1991] C. J. Hirschmugl, M. Sagurton, and G. P. Williams, Multiparticle coherence calculations for synchrotron-radiation emission, Physical Review A 44, 1316 (1991).


# Accelerated Almost-Sure Convergence Rates for Nonconvex Stochastic Gradient
Descent using Stochastic Learning Rates

Theodoros Mamalis
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
306 N Wright St, Urbana, IL 61801, USA
<EMAIL_ADDRESS>
Dušan Stipanović
Coordinated Science Laboratory
University of Illinois at Urbana-Champaign
1308 W Main St, Urbana, IL 61801, USA
<EMAIL_ADDRESS>
Petros Voulgaris
Department of Mechanical Engineering
University of Nevada
Reno, NV 89557, USA
<EMAIL_ADDRESS>

###### Abstract

Large-scale optimization problems require algorithms both effective and
efficient. One such popular and proven algorithm is Stochastic Gradient
Descent which uses first-order gradient information to solve these problems.
This paper studies almost-sure convergence rates of the Stochastic Gradient
Descent method when instead of deterministic, its learning rate becomes
stochastic. In particular, its learning rate is equipped with a multiplicative
stochasticity, producing a stochastic learning rate scheme. Theoretical
results show accelerated almost-sure convergence rates of Stochastic Gradient
Descent in a nonconvex setting when using an appropriate stochastic learning
rate, compared to a deterministic-learning-rate scheme. The theoretical
results are verified empirically.

00footnotetext: This work is supported by the grant from the National Robotics
Initiative grant titled “NRI: FND:COLLAB: Multi-Vehicle Systems for Collecting
Shadow-Free Imagery in Precision Agriculture” (grant no.2019-04791/project
accession no. 1020285) from the USDA National Institute of Food and
Agriculture.

##  1 Introduction

Solving large-scale optimization problems usually requires the optimization
algorithm to process large amounts of data which can lead to long
computational times as well as large memory requirements. For this reason,
simple and cost-effective algorithms need to be used. The most prominent
examples are the so-called gradient algorithms which utilize gradient
information to iteratively estimate a minimizer for the optimization problem,
with perhaps the most prominent algorithm being Stochastic Gradient Descent
(SGD), initially introduced in Robbins and Monro (1951).

Even though in most optimization algorithms (including SGD) commonly the
learning rate $\eta_{k}$ (where $k$ is the iteration count) also referred to
as step size, is taken to be deterministic, the novelty in this work is that
it introduces the problem where the learning rate becomes stochastic by
equipping it with multiplicative stochasticity. In general, it has been
observed that minimization performance can be noticeably improved under
appropriate learning schemes e.g., under deterministic adaptive learning rate
schemes. Examples include ADAM Kingma and Ba (2015) and some variants (e.g.,
AMSGrad Reddi et al. (2018) or ADAMW Loshchilov and Hutter (2019)) or
precursors (e.g., McMahan and Streeter (2010), Duchi et al. (2011)). This work
demonstrates that performance can be significantly improved if instead of just
adaptive, the learning rate becomes both adaptive and stochastic.

In specific, the learning rate instead of $\eta_{k}$ now becomes
$\eta_{k}u_{k}$ (where e.g., $\eta_{k}=\eta/\sqrt{k}$ or $\eta_{k}=\eta$, with
$\eta$ a positive constant; with some abuse of terminology, $\eta_{k}$ will be
referred to as step size) and where $u_{k}$ is a random variable, referred to
as stochasticity factor (SF) in the rest of the paper. Because of the
multiplicative nature of the SF the stochastic learning rate examined in this
work will be referred to as Multiplicative-Stochastic-Learning-Rate (MSLR). A
stochastic learning rate whose SF is a uniformly distributed random variable
at each iteration will be referred to as Uniform-Multiplicative-Stochastic-
Learning-Rate (UMSLR). This work uses MSLR on SGD to prove accelerated almost
sure convergence rates in a nonconvex and smooth setting compared to a
deterministic learning rate.

The SGD algorithm has been a traditional topic of research investigated in
numerous works, e.g., Bertsekas and Tsitsiklis (2000); Zhou et al. (2017),
Loizou and Richtárik (2018). In Mertikopoulos et al. (2020) it is shown that
the gradient norm of SGD converges almost surely (a.s.). Loizou et al. (2021)
show convergence without knowledge of the smoothness constant using Line-
Search Nocedal and Wright (2006) and Polyak stepsizes Polyak (1987). Almost
sure convergence rates have been provided in works such as Bottou (2003);
Nguyen et al. (2018). The authors in Sebbouh et al. (2021) derive almost sure
convergence rates for the minimum squared gradient norm of SGD in a noncovex
and smooth setting by utilizing a convergence result from Robbins and Siegmund
(1971). In-expectation convergence analyses have been made in works such as
Nemirovski et al. (2009); Moulines and Bach (2011); Bottou et al. (2018) and
references therein. In-expectation convergence analysis of SGD for stochastic-
learning-rates was made in Mamalis et al. (2021).

In summary, this work provides accelerated a.s. convergence rates for SGD in
the nonconvex and smooth setting using MSLR, compared to the deterministic
learning rate case. Experiments demonstrate the improved a.s. convergence
rates empirically. In more detail, the main contributions of this paper are:

  * •

The introduction of the notion of stochastic learning rate schemes. Note that
in this work a stochastic learning rate scheme should not depend on the
stochasticity induced by the samples and how they are processed (e.g., as is
usually the case with the computation of the gradients in most of the
stochastic gradient methods). The stochasticity in the learning rates should
be able to be directly controlled to be of any distribution, a requirement
whose importance is discussed in the next point. It should be noted that this
is in contrast to the stochasticity induced by randomly sampling the dataset
which can be unable or more difficult to possess a (discrete) distribution
with any prespecified property, regardless of the sampling patterns.

  * •

Accelerated a.s. convergence rates for the SGD algorithm. The introduction of
stochastic learning rate schemes can be rigorously shown to provide better
convergence rates than the deterministic learning rate versions of the SGD
algorithm in the nonconvex and smooth settings for the latter. In specific,
moments of the distribution of the SF enter the a.s. convergence rate of SGD,
directly affecting its rates. This means that by choosing the distribution of
the learning rate stochasticity, i.e., of the SF, to possess appropriate
prespecified properties, the a.s. convergence rates of the resulting
stochastic learning rate algorithm can be improved compared to its
deterministic counterpart. In absence of an SF the a.s. convergence rates
reduce to those of the deterministic learning rate algorithms as expected.

  * •

Empirically demonstrating that MSLR schemes, and in specific UMSLR, exhibit
significantly improved optimization performance for SGD in accordance to the
theoretical results, for some popular datasets.

The remainder of the paper is organized as follows. Section 2 states the
context of this work in mathematical terms, along with a lemma and necessary
assumption. The mathematical derivation of the almost sure convergence rates
of the SGD algorithm with MSLR is given in Section 3. Section 4 constructs an
appropriate SF which provides accelerated a.s. convergence rates for SGD, and
provides a discussion on selecting hyperparameters that complement the SF
distribution in accelerating performance. In Section 5, the experimental
results for SGD using a UMSLR scheme are presented and compared to the
deterministic-learning rate case. Section 6 concludes the paper with avenues
of future work.

##  2 Problem Formulation and Assumptions

Let $v$ be a random variable with distribution $D$, $X$ a set in
$\mathbb{R}^{d}$, and $f_{v}(x)$ a function that depends on $v$ and $x\in X$.
Then the optimization problem is:

$\mathop{\min}\limits_{x\in{\mathbb{R}^{d}}}\mathbb{E}_{v\sim D}[f_{v}(x)],$
(1)

Define $f(x):=\mathbb{E}_{v\sim D}[f_{v}(x)]$. In the well-known case of
Empirical Risk Minimization (ERM) $\mathbb{E}_{v\sim
D}[f_{v}(x)]=\frac{1}{n}\sum\nolimits_{i=1}^{n}{f_{v_{i}}({x})}$, where $v$
represents a random sample from the available training data and $x$ the
parameters to be learned. Assume $f$ is smooth with $L>0$ being its smoothness
constant. It is assumed that at least one minimizer $x_{*}$ to (1) exists
yielding $f_{*}$. Then, the SGD algorithm is given by:

${x_{k+1}}={x_{k}}-{\eta_{k}}u_{k}\nabla{f_{{v_{k}}}}({x_{k}}).$ (2)

The stochastic learning rate is $\eta_{k}u_{k}$ where $u_{k}$ denotes the SF,
and $\eta_{k}$ is deterministic and will be referred to as stepsize. This
learning rate scheme will be referred to as MSLR. Typical assumptions made in
the context of stochastic approximations include either bounded gradients or
bounded variance of the gradients. Below, a more general assumption is given:

######  Assumption 1 (Expected Smoothness).

There exist constants A,B,C s.t. for all $x\in\mathbb{R}^{d}$:

$\mathbb{E}_{v}[\left\|\nabla f_{v}(x)\right\|^{2}]\leq
A(f(x)-f_{*})+B\left\|\nabla f(x)\right\|^{2}+C.$ (3)

This assumption is introduced in Khaled and Richtárik (2020) where is called
Expected Smoothness and wherein the properties and significance of this
assumption, especially for settings such as ERM, are discussed. Next, a lemma
is presented:

######  Lemma 1.

Consider a filtration $(F_{k})_{k}$, the nonnegative sequences of
$(F_{k})_{k}$-adapted processes $(V_{k})_{k}$, $(U_{k})_{k}$ and
$(Z_{k})_{k}$, and a sequence of positive numbers $(\gamma_{k})_{k}$ such that
$\sum\nolimits_{k}Z_{k}<\infty$ almost surely and
$\prod\nolimits_{k}(1+\gamma_{k})<\infty$ , and:

$\forall
k\in\mathbb{N},\,\,\mathbb{E}[{V_{k+1}}|{F_{k}}]+{U_{k+1}}\leq(1+{\gamma_{k}}){V_{k}}+{Z_{k}}.$
(4)

Then $({V_{k}})_{k}$ converges and $\sum\nolimits_{k}U_{k}<\infty$ almost
surely.

This lemma (Robbins and Siegmund (1971)) is used extensively in the proofs of
the theorems of this paper. The following assumption includes standard
conditions for the step size that appear in the stochastic approximations
literature and which usually hold in practice.

######  Assumption 2.

The sequence ${({\eta_{k}})_{k}}$ is decreasing,
$\sum\nolimits_{k}{{\eta_{k}}}=\infty$ ,
$\sum\nolimits_{k}{\eta_{k}^{2}}<\infty$ and
$\sum\nolimits_{k}{\frac{{{\eta_{k}}}}{{\sum\nolimits_{j=0}^{k-1}{{\eta_{j}}}}}}=\infty$.

Moreover, for the expected value of the SF the following assumption is made.

######  Assumption 3.

The sequence $\mathbb{E}_{u}[u_{k}]$ is monotone.

At this point it is noted that distributions for which (3) holds are able to
be constructed. Discussion on the distribution constructed in this work is
deferred to Section 4.

##  3 Accelerated Nonconvex SGD Almost-Sure Convergence Rates

This sections presents results for accelerated a.s. convergence rates of the
SGD algorithm in the nonconvex case. The first result is formulated as
follows:

######  Theorem 1.

Consider the iterates of (2). Assume that Assumption 1 holds. Assume that the
stochasticity factor is bounded, i.e., $0<u_{k}\leq c_{2}$ with
$c_{2}:=\sup_{k}u_{k}$. Assume that the first moment of the stochasticity
factor is bounded, i.e., $0<\mu_{1}\leq\mathbb{E}_{u}[u_{k}]$ with
$\mu_{1}:=\inf_{k}\mathbb{E}_{u}[u_{k}]$. Choose stochasticity factor $u_{k}$
which satisfies 3. Assume that the stepsizes verify 2.

1.1a. If $\mathbb{E}_{u}[u_{k}]$ is decreasing, if $Var_{u}[u_{k}]$ is
increasing, if $\mathbb{E}_{u}[u_{k}]>Var_{u}[u_{k}]+1$, and if
$0\leq\eta_{k}\leq 1/(BL\mathbb{E}_{u}[u_{k}])$ for all $k\in\mathbb{N}$,
then:

$\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}=o\left({\frac{(\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}])^{-1}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (5)

1.1b. If $\mathbb{E}_{u}[u_{k}]$ is decreasing, and if $0\leq\eta_{k}\leq
1/(BLc_{2})$ for all $k\in\mathbb{N}$, then:

$\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}=o\left({\frac{1}{\mathbb{E}_{u}[u_{k}]{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (6)

1.2. If $\mathbb{E}_{u}[u_{k}]$ is increasing, if $Var_{u}[u_{k}]$ is
decreasing, if $\mathbb{E}_{u}[u_{k}]<1$, if
$\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]}<1$, and if $0\leq\eta_{k}\leq
1/(BL)$ for all $k\in\mathbb{N}$, then:

$\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}=o\left(\frac{\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}]}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}\right)\quad
a.s.$ (7)

Several remarks on the SGD convergence rate results in the nonconvex case are
in order. First, the assumptions of Theorem 1 guarantee the a.s. convergence
rates presented in the theorem. However, whether the MSLR a.s. convergence
rates are accelerated or not compared to the deterministic-learning-rate case,
whose rate is $o\left((\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}})^{-1}\right)$
(Sebbouh et al. (2021)), depends on the choice of the SF distribution of MSLR
SGD. To that end, it can be readily observed what properties the SF needs to
satisfy so that the MSLR scheme produces faster a.s. convergence rates than
the deterministic-learning-rate case. Firstly, for 1.1a, for the moments of
the SF it should be that $\mathbb{E}_{u}[u_{k}]>Var_{u}[u_{k}]+1$. Secondly,
for 1.1b, it should be that $\mathbb{E}_{u}[u_{k}]>1$ and thirdly, for 1.2, it
should be that $\mathbb{E}_{u}[u_{k}]<Var_{u}[u_{k}]+1$. However, the last
condition can be equivalently written as
$0<\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})<1$.
This is implied by the two conditions $\mathbb{E}_{u}[u_{k}]<1$ and
$\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]}<1$ (for 1.2, these two
acceleration conditions happen to also be theorem assumptions, but this is not
true in general), given that $Var_{u}[u_{k}]\geq 0$. The reason that the SF is
taken to satisfy these two conditions instead of
$\mathbb{E}_{u}[u_{k}]<Var_{u}[u_{k}]+1$, which is a weaker condition, is
because in practice they can be more easily checked for adaptive
distributions, e.g., as in the case of a uniformly distributed SF discussed in
Section 4 in more detail.

Second, the requirements of Theorem 1 are sufficient but not necessary, i.e.,
they can be replaced by weaker assumptions and Theorem 1 will still hold.
Nonetheless, the weaker assumptions are not as easily verified theoretically,
and perhaps experimentally, as the assumptions currently given. For example,
the mean $\mathbb{E}_{u}[u_{k}]$ and variance $Var_{u}[u_{k}]$ monotonicity
assumptions along with the assumptions that follow them in 1.1a and 1.2 could
be replaced by the assumptions
$Var_{u}[u_{k+1}]-Var_{u}[u_{k}]>\mathbb{E}_{u}[u_{k+1}]-\mathbb{E}_{u}[u_{k}]$
and
$Var_{u}[u_{k+1}]-Var_{u}[u_{k}]<\mathbb{E}_{u}[u_{k+1}]-\mathbb{E}_{u}[u_{k}]$
respectively. These are satisfied when respectively
$Var^{\prime}_{u}[u_{k}]>E^{\prime}_{u}[u_{k}]$ and
$Var^{\prime}_{u}[u_{k}]>E^{\prime}_{u}[u_{k}]$ hold, where the derivatives
are with respect to $k$. This is since if, e.g.,
$Var^{\prime}_{u}[u_{k}]>E^{\prime}_{u}[u_{k}]$ then
$\frac{Var_{u}[u_{k+1}]-Var_{u}[u_{k}]}{k+1-k}>\frac{\mathbb{E}_{u}[u_{k+1}]-\mathbb{E}_{u}[u_{k}]}{k+1-k}$
which gives the required weaker assumption for 1.1a (respectively for 1.2 by
replacing $>$ with $<$ in the previous). However, given that checking
assumptions which include both the derivatives of the mean and variance of
some adaptive distributions can become complex quickly, the current
assumptions that consider the monotonicity of each of the mean and variance
separately, are deemed simpler to check than the assumptions dealing with a
combination of the derivatives of these moments.

Third, it is noted that the various requirements that appear in Theorem 1 are
consistent. In 1.1a, $Var_{u}[u_{k}]$ cannot escape to infinity since it is
less than a decreasing and positive $\mathbb{E}_{u}[u_{k}]$. In 1.1b,
$\mathbb{E}_{u}[u_{k}]$ cannot diverge to negative infinity since it is
positive, and in 1.2, $\mathbb{E}_{u}[u_{k}]$ cannot diverge to infinity since
it is less than unity. Moreover, in the denominator of 1.1a the difference
$\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}]$ appears whereas in 1.1b the larger
quantity $\mathbb{E}_{u}[u_{k}]$ appears. This should not be taken that 1.1b
provides faster convergence rates than 1.1a since in case 1.1a the stepsize,
and therefore the term ${{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}$, is larger
than in case 1.1b so there is a trade-off between the acceleration provided by
1.1a and 1.1b (e.g., if the stepsizes for cases 1.1a and 1.1b are
$\bar{\eta}_{k}=\frac{1}{BL\mathbb{E}_{u}[u_{k}]}$ and
$\eta$${}_{k}=\frac{1}{BLc_{2}}$ respectively, and, assuming a common SF
$u_{k}$ for both cases, it is that
$1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]}\geq\frac{1}{c_{2}}$, then the
former gives faster convergence rates since then
$({(\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}]){\sum\nolimits_{t=0}^{k-1}{{\bar{\eta}_{t}}}}})^{-1}\geq$($\mathbb{E}_{u}[u_{k}]\sum\nolimits_{t=0}^{k-1}$
$\eta$ ${}_{t})^{-1})$.

Finally, when the SF becomes constant unity, the deterministic-learning-rate
a.s. convergence rate is recovered by the MSLR SGD a.s. convergence rates in
Theorem 1 since for $u_{k}=1$ it is $\mathbb{E}_{u}[u_{k}]=1$ and
$Var_{u}[u_{k}]=0$ yielding
$o\left((\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}})^{-1}\right)$.

All in all, Theorem 1 demonstrates that for appropriate choices of SFs the
MSLR scheme accelerates the a.s. convergence rates of SGD compared to the a.s.
convergence rates of its deterministic-learning-rate counterpart.

###### Proof.

The proof follows the proof of Lemma 2 in Khaled and Richtárik (2020).
Starting with (2), equation (46) in Khaled and Richtárik (2020) becomes:

$\displaystyle f(x_{k+1})$ $\displaystyle\leq f(x_{k})+\left\langle{\nabla
f(x_{k}),x_{k+1}-x_{k}}\right\rangle+\frac{L}{2}\left\|x_{k+1}-x_{k}\right\|^{2}$
(8) $\displaystyle=f(x_{k})-u_{k}\eta_{k}\left\langle{\nabla
f(x_{k}),g(x_{k})}\right\rangle+\frac{Lu_{k}^{2}\eta_{k}^{2}}{2}\left\|g(x_{k})\right\|^{2}$

which ultimately results in:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{\eta_{k}}{2}(2u_{k}-u^{2}_{k}LB\eta_{k})\left\|\nabla
f(x_{k})\right\|^{2}$ (9)
$\displaystyle\leq(1+u_{k}^{2}\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{u_{k}^{2}\eta_{k}^{2}LC}{2}.$

###  3.1 Case 1a: $\mathbb{E}_{u}[u_{k+1}]\leq\mathbb{E}_{u}[u_{k}]$ and
$\eta_{k}\leq\frac{1}{LB\mathbb{E}_{u}[u_{k}]}$.

Using $\eta_{k}\leq 1/(BL\mathbb{E}_{u}[u_{k}])$ in (9):

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{\eta_{k}}{2}(2u_{k}-\frac{u^{2}_{k}}{\mathbb{E}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}\leq(1+u_{k}^{2}\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{u_{k}^{2}\eta_{k}^{2}LC}{2}.$
(10)

From $u_{k}\leq c_{2}$ and Assumption 2 it is that
$\sum\nolimits_{k=0}^{\infty}\frac{{u_{k}^{2}\eta_{k}^{2}LC}}{2}<\sum\nolimits_{k=0}^{\infty}\frac{{c_{2}^{2}\eta_{k}^{2}LC}}{2}<\infty$.
Also it is that $\sum\nolimits_{k=0}^{\infty}{\eta_{k}^{2}}<\infty$, which
means
$\prod\nolimits_{k=0}^{\infty}{(1+{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL)}<\prod\nolimits_{k=0}^{\infty}{(1+c_{2}^{2}\eta_{k}^{2}AL)}<\infty$.
Thus, from Lemma 1, $f(x_{k})-f_{*}$ converges a.s. Taking expectations with
respect to $u$ yields:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{\eta_{k}}{2}(2\mathbb{E}_{u}[u_{k}]-\frac{\mathbb{E}_{u}[u^{2}_{k}]}{\mathbb{E}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}$ (11)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Using $\mathbb{E}_{u}[u^{2}_{k}]=Var_{u}[u_{k}]+\mathbb{E}_{u}[u_{k}]^{2}$:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}]\frac{\eta_{k}}{2}(2-\frac{\mathbb{E}_{u}^{2}[u_{k}]+Var_{u}[u_{k}]}{\mathbb{E}^{2}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}$ (12)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

This means:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}]\frac{\eta_{k}}{2}(1-\frac{Var_{u}[u_{k}]}{\mathbb{E}^{2}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}$ (13)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Since $\mathbb{E}_{u}[u_{k}]>Var_{u}[u_{k}]+1$ from the assumptions of the
theorem, it is that $\mathbb{E}_{u}[u_{k}]\geq 1$, which yields
$\mathbb{E}^{2}_{u}[u_{k}]\geq\mathbb{E}_{u}[u_{k}]$ or, equivalently,
$-\frac{Var_{u}[u_{k}]}{\mathbb{E}^{2}_{u}[u_{k}]}\geq-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]}$,
since $Var_{u}[u_{k}]\geq 0$. Thus:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}]\frac{\eta_{k}}{2}(1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}$ (14)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Then, let:

$\displaystyle{w_{k}}=\frac{{2{\eta_{k}}}}{{\sum\nolimits_{t=0}^{k}{{\eta_{t}}}}},\quad{g_{0}}={\left\|{\nabla
f({x_{0}})}\right\|^{2}},$ (15)
$\displaystyle{g_{k+1}}=(1-{w_{k}}){g_{k}}+{w_{k}}{\left\|{\nabla
f({x_{k}})}\right\|^{2}}$

for all $k\in\mathbb{N}$. Moreover, since $g_{k}$ is a linear combination of
${\left\|{\nabla f({x_{t}})}\right\|^{2}},t=0,\cdots,k-1$ it is that:

${g_{k}}=\sum\nolimits_{t=0}^{k-1}{{\tilde{w}_{t}}}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}$ (16)

for some sequence ${({\tilde{w}_{t}})_{t}}$ with
$\sum\nolimits_{t=0}^{k-1}{{\tilde{w}_{t}}}=1$, and where
$0\leq\tilde{w}_{t}\leq 1$ since $\eta_{t}$ is decreasing. Then, using (15) to
replace ${\left\|{\nabla f({x_{k}})}\right\|^{2}}$ in (14) yields:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k+1}+\frac{\eta_{k}}{2}\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})g_{k}$
(17)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Since $\mathbb{E}_{u}[u_{k}]\geq\mathbb{E}_{u}[u_{k+1}]$ and
$Var_{u}[u_{k}]\leq Var_{u}[u_{k+1}]$:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k+1}](1-\frac{Var_{u}[u_{k+1}]}{\mathbb{E}_{u}[u_{k+1}]})\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k+1}+\frac{\eta_{k}}{2}\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})g_{k}$
(18)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}$

and since $(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)>1$:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k+1}](1-\frac{Var_{u}[u_{k+1}]}{\mathbb{E}_{u}[u_{k+1}]})\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k+1}+\frac{\eta_{k}}{2}\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})g_{k}$
(19)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)\mathbb{E}_{u}[u_{k}]\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Or equivalently:

$\displaystyle\mathbb{E}_{k}[(f(x_{k+1})-f_{*})+\varphi_{1}(k+1)]+\frac{\eta_{k}}{2}\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})g_{k}$
(20)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)((f(x_{k})-f_{*})+\varphi_{1}(k))+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}$

where
$\varphi_{1}(k):=\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}$.
Then, from $u_{k}\leq c_{2}$ which gives $\mathbb{E}_{u}[u^{2}_{k}]\leq
c^{2}_{2}$, and from Assumption 2 it is that
$\sum\nolimits_{k=0}^{\infty}{{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL}<{c_{2}^{2}}AL\sum\nolimits_{k=0}^{\infty}{\eta_{k}^{2}}<\infty$,
which means
$\prod\nolimits_{k=0}^{\infty}{(1+{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL)}<\infty$.
Moreover, it is that
$\frac{c_{2}^{2}LC}{2}\sum\nolimits_{k=0}^{\infty}\eta_{k}^{2}<\infty$ from
Assumption 2. Then, from Lemma 1 this means that
$\sum\nolimits_{t=0}^{\infty}{{\eta_{t}}}\mathbb{E}_{u}[u_{t}](1-\frac{Var_{u}[u_{t}]}{\mathbb{E}_{u}[u_{t}]})g_{t}<\infty$
a.s. and also that:

$\left((f(x_{k})-f_{*})+\varphi_{1}(k)\right)\text{converges a.s. }$

This gives that $(\varphi_{1}(k))_{k}$ converges a.s. since it is that
$(f(x_{k+1})-f_{*})$ converges a.s. Then, algebraically manipulating
$\mathop{\lim}\limits_{k\to\infty}\varphi_{1}(k)$ it is that:

$\displaystyle\mathop{\lim}\limits_{k\to\infty}\frac{{{\eta_{k}}}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}{g_{k}}=\mathop{\lim}\limits_{k\to\infty}{{\eta_{k}}}\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})g_{k}=0.$
(21)

Thus,
$\mathop{\lim}\limits_{k\to\infty}\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}{g_{k}}=0$
from Assumption 2, i.e., from
$\sum\nolimits_{k=0}{\frac{{{\eta_{k}}}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}=\infty$.
Therefore:

${g_{k}}=o\left({\frac{1}{{\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (22)

that is:

${g_{k}}=o\left({\frac{1}{(\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}]){\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (23)

Moreover, from (16) it is that
$g_{k}\geq\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}\geq 0$, which yields:

$\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}=o\left({\frac{(\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}])^{-1}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right),$
(24)

almost surely.

###  3.2 Case 1b: $\mathbb{E}_{u}[u_{k+1}]\leq\mathbb{E}_{u}[u_{k}]$ and
$\eta_{k}\leq\frac{1}{LBc_{2}}$.

Using $u_{k}\leq c_{2}$ in (9):

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{u_{k}\eta_{k}}{2}(2-c_{2}LB\eta_{k})\left\|\nabla
f(x_{k})\right\|^{2}\leq(1+u_{k}^{2}\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{u_{k}^{2}\eta_{k}^{2}LC}{2}.$
(25)

Using $\eta_{k}\leq 1/(LBc_{2})$ results in:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{u_{k}\eta_{k}}{2}\left\|\nabla
f(x_{k})\right\|^{2}\leq(1+u_{k}^{2}\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{u_{k}^{2}\eta_{k}^{2}LC}{2}.$
(26)

By taking expectations with respect to $u$:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{\mathbb{E}_{u}[u_{k}]\eta_{k}}{2}\left\|\nabla
f(x_{k})\right\|^{2}$ (27)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

From Assumption 2 it is that
$\sum\nolimits_{k=0}^{\infty}\frac{{u_{k}^{2}\eta_{k}^{2}LC}}{2}<\sum\nolimits_{k=0}^{\infty}\frac{{c_{2}^{2}\eta_{k}^{2}LC}}{2}<\infty$.
Also it is that $\sum\nolimits_{k=0}^{\infty}{\eta_{k}^{2}}<\infty$, which
means
$\prod\nolimits_{k=0}^{\infty}{(1+{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL)}<\prod\nolimits_{k=0}^{\infty}{(1+c_{2}^{2}\eta_{k}^{2}AL)}<\infty$.
Thus from Lemma 1, $f(x_{k})-f_{*}$ converges a.s. Using (15) to replace
${\left\|{\nabla f({x_{k}})}\right\|^{2}}$ in (27) gives:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}]\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k+1}+\frac{\eta_{k}}{2}\mathbb{E}_{u}[u_{k}]g_{k}$
(28)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\mathbb{E}_{u}[u_{k}]\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Since $\mathbb{E}_{u}[u_{k}]\geq\mathbb{E}_{u}[u_{k+1}]$:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k+1}]\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k+1}+\frac{\eta_{k}}{2}\mathbb{E}_{u}[u_{k}]g_{k}$
(29)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]^{2}})\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}$

and since $(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)>1$:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}+\varphi_{2}(k+1)]+\frac{\eta_{k}}{2}\mathbb{E}_{u}[u_{k}]g_{k}$
(30)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)\left((f(x_{k})-f_{*})+\varphi_{2}\right)+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}$

where
$\varphi_{2}(k)=\mathbb{E}_{u}[u_{k}]\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}$.
Then from $u_{k}\leq c_{2}$ which gives $\mathbb{E}_{u}[u^{2}_{k}]\leq
c^{2}_{2}$ and from Assumption 2 it is that
$\sum\nolimits_{k=0}^{\infty}{{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL}<{c_{2}^{2}}AL\sum\nolimits_{k=0}^{\infty}{\eta_{k}^{2}}<\infty$,
which means
$\prod\nolimits_{k=0}^{\infty}{(1+{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL)}<\infty$.
Moreover, it is that
$\frac{\mathbb{E}_{u}[u_{k}^{2}]LC}{2}\sum\nolimits_{k=0}^{\infty}\eta_{k}^{2}<\frac{c_{2}^{2}LC}{2}\sum\nolimits_{k=0}^{\infty}\eta_{k}^{2}<\infty$
from Assumption 2. Then, from Lemma 1 this means that
$\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}\mathbb{E}_{u}[u_{t}]g_{t}<\infty$ a.s.
and also that
$((f(x_{k})-f_{*})+\mathbb{E}_{u}[u_{k}]\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k})$
converges a.s. This gives that $({\varphi_{2}(k)})_{k}$ converges a.s. since
it is also that $(f(x_{k+1})-f_{*})$ converges a.s. This yields for
$\mathop{\lim}\limits_{k\to\infty}\varphi_{2}(k)$:

$\mathop{\lim}\limits_{k\to\infty}\frac{{{\eta_{k}}}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}\mathbb{E}_{u}[u_{k}]\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}{g_{k}}=\mathop{\lim}\limits_{k\to\infty}{{\eta_{k}}}\mathbb{E}_{u}[u_{k}]g_{k}=0.$

This means that
$\mathop{\lim}\limits_{k\to\infty}\mathbb{E}_{u}[u_{k}]\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}{g_{k}}=0$
from Assumption 2, i.e., from
$\sum\nolimits_{k=0}{\frac{{{\eta_{k}}}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}=\infty$.
Therefore:

${g_{k}}=o\left({\frac{1}{{\mathbb{E}_{u}[u_{k}]\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (31)

Moreover, from (16) it is that
$g_{k}\geq\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}\geq 0$, which yields:

$\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}=o\left({\frac{1}{\mathbb{E}_{u}[u_{k}]{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (32)

###  3.3 Case 2: $\mathbb{E}_{u}[u_{k}]\leq\mathbb{E}_{u}[u_{k+1}]$ and
$\eta_{k}\leq\frac{1}{BL}$.

Using $\eta_{k}\leq 1/(BL)$ in (9):

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{\eta_{k}}{2}(2u_{k}-u^{2}_{k})\left\|\nabla
f(x_{k})\right\|^{2}\leq(1+u_{k}^{2}\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{u_{k}^{2}\eta_{k}^{2}LC}{2}.$
(33)

From $u_{k}\leq c_{2}$ and Assumption 2 it is that
$\sum\nolimits_{k=0}^{\infty}\frac{{u_{k}^{2}\eta_{k}^{2}LC}}{2}<\sum\nolimits_{k=0}^{\infty}\frac{{c_{2}^{2}\eta_{k}^{2}LC}}{2}<\infty$.
Also it is that $\sum\nolimits_{k=0}^{\infty}{\eta_{k}^{2}}<\infty$, which
means
$\prod\nolimits_{k=0}^{\infty}{(1+{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL)}<\prod\nolimits_{k=0}^{\infty}{(1+c_{2}^{2}\eta_{k}^{2}AL)}<\infty$.
Thus, from Lemma 1, $f(x_{k})-f_{*}$ converges a.s. Taking expectations with
respect to $u$ yields:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\frac{\eta_{k}}{2}(2\mathbb{E}_{u}[u_{k}]-\mathbb{E}_{u}[u^{2}_{k}])\left\|\nabla
f(x_{k})\right\|^{2}$ (34)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Using $\mathbb{E}_{u}[u^{2}_{k}]=Var_{u}[u_{k}]+\mathbb{E}_{u}[u_{k}]^{2}$:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}]\frac{\eta_{k}}{2}(2-\frac{\mathbb{E}_{u}^{2}[u_{k}]+Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}$ (35)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

This means:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}]\frac{\eta_{k}}{2}(2-\mathbb{E}_{u}[u_{k}]-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}$ (36)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Since $\mathbb{E}_{u}[u_{k}]<1$ from the assumptions of the theorem:

$\displaystyle\mathbb{E}_{k}[f(x_{k+1})-f_{*}]+\mathbb{E}_{u}[u_{k}]\frac{\eta_{k}}{2}(1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})\left\|\nabla
f(x_{k})\right\|^{2}$ (37)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2}.$

Then, using (15) to replace ${\left\|{\nabla f({x_{k}})}\right\|^{2}}$ in (37)
yields (LABEL:eq:eq_for_case1.2). Denoting
$\psi_{k}:=\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})$,
dividing (LABEL:eq:eq_for_case1.2) by $\psi_{k}^{2}$ and since
$(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)>1$:

$\displaystyle\mathbb{E}_{k}[\frac{1}{\psi^{2}_{k}}(f(x_{k+1})-f_{*})]+\frac{1}{\psi_{k}}\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k+1}+\frac{\eta_{k}}{2}\frac{g_{k}}{\psi_{k}}$
(38)
$\displaystyle\leq\frac{(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)}{\psi_{k}^{2}}(f(x_{k})-f_{*})+\frac{(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)}{\psi_{k}}\frac{\sum\nolimits_{t=0}^{k-1}{\eta_{t}}}{2}g_{k}+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2\psi_{k}^{2}}.$

Since $\mathbb{E}_{u}[u_{k}]\leq\mathbb{E}_{u}[u_{k+1}]$ which means
$\frac{1}{\mathbb{E}_{u}[u_{k}]}\geq\frac{1}{\mathbb{E}_{u}[u_{k+1}]}$ and
since $Var_{u}[u_{k+1}]\leq Var_{u}[u_{k}]$ it is that:

$\frac{1}{\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})}\geq\frac{1}{\mathbb{E}_{u}[u_{k+1}](1-\frac{Var_{u}[u_{k+1}]}{\mathbb{E}_{u}[u_{k+1}]})}$
(39)

which means $(\psi_{k})^{-1}\geq(\psi_{k+1})^{-1}$. This yields:

$\displaystyle\mathbb{E}_{k}[\frac{1}{\psi_{k+1}}(f(x_{k+1})-f_{*})+\frac{1}{\psi_{k+1}}\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k+1}]+\frac{\eta_{k}g_{k}}{2\psi_{k}}$
(40)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)\psi(k)+\eta_{k}^{2}\frac{c_{2}^{2}LC}{2N}$

where
$\psi_{k}\geq\frac{c_{2}^{2}}{\mu_{1}^{2}}(\mu_{1}+\mu_{1}^{2}-c_{2}^{2})^{2}:=N$
for all $k$, from using
$Var_{u}[u_{k}]=\mathbb{E}_{u}[u^{2}_{k}]-\mathbb{E}_{u}[u_{k}^{2}]$, then
using $\mathbb{E}_{u}[u^{2}_{k}]\leq c_{2}^{2}$ and
$\mathbb{E}_{u}[u_{k}]\leq\mu_{1}$, and doing some algebra. Then, from
$\mathbb{E}_{u}[u_{k}^{2}]\leq c_{2}^{2}$ and from Assumption 2 it is that
$\sum\nolimits_{k=0}^{\infty}{{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL}<{c^{2}}AL\sum\nolimits_{k=0}^{\infty}{\eta_{k}^{2}}<\infty$,
which means
$\prod\nolimits_{k=0}^{\infty}{(1+{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL)}<\infty$.
Moreover, it is that
$\frac{c_{2}^{2}LC}{2N}\sum\nolimits_{k=0}^{\infty}\eta_{k}^{2}<\infty$ from
Assumption 2. Then, from Lemma 1 this means that
$\sum\nolimits_{t=0}^{k-1}\frac{{{\eta_{t}}}g_{t}}{\psi_{t}}<\infty$ a.s. and:

$\left(\frac{1}{\psi^{2}_{k}}(f(x_{k})-f_{*})+\frac{1}{\psi_{k}}\frac{\sum\nolimits_{t=0}^{k}{\eta_{t}}}{2}g_{k}\right)\text{converges
a.s. }$ (41)

Note that from (10), by dividing by $\psi_{k}^{2}$ and using (39):

$\displaystyle\mathbb{E}_{k}[\frac{1}{\psi_{k+1}^{2}}(f(x_{k+1})-f_{*})]+\frac{1}{\psi_{k}}\left\|\nabla
f(x_{k})\right\|^{2}$ (42)
$\displaystyle\leq(1+\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}AL)\frac{1}{\psi_{k}^{2}}(f(x_{k})-f_{*})+\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2\psi_{k}^{2}}.$

From $\mathbb{E}_{u}[u_{k}^{2}]\leq c_{2}^{2}$ and Assumption 2 it is that
$\sum\nolimits_{t=0}^{k-1}\frac{\mathbb{E}_{u}[u_{k}^{2}]\eta_{k}^{2}LC}{2{\psi_{k}^{2}}}\leq\frac{c_{2}^{2}LC}{2N}\sum\nolimits_{t=0}^{k-1}\eta_{k}^{2}<\infty$.
Also, from Assumption 2 it is that
$\sum\nolimits_{k=0}^{\infty}{{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL}<{c^{2}}AL\sum\nolimits_{k=0}^{\infty}{\eta_{k}^{2}}<\infty$
which gives
$\prod\nolimits_{k=0}^{\infty}{(1+{\mathbb{E}_{u}}[u_{k}^{2}]\eta_{k}^{2}AL)}<\infty$.
Then from Lemma 1 it is that $\frac{1}{\psi_{k}^{2}}(f(x_{k})-f_{*})$
converges a.s. This means from (41) that
${\left({\left(\frac{1}{\psi_{k}}{\frac{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}{2}}\right){g_{k}}}\right)_{k}}$
converges a.s. This yields:

$\mathop{\lim}\limits_{k\to\infty}\frac{{{\eta_{k}}}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}\frac{1}{\psi_{k}}\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}{g_{k}}=\mathop{\lim}\limits_{k\to\infty}\frac{\eta_{k}g_{k}}{\psi_{k}}=0.$

This means that
$\mathop{\lim}\limits_{k\to\infty}\frac{1}{\psi_{k}}\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}{g_{k}}=0$
from Assumption 2, i.e., from
$\sum\nolimits_{k=0}{\frac{{{\eta_{k}}}}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}=\infty$.
Therefore, using the definition of $\psi_{k}$ it is that:

${g_{k}}=o\left({\frac{\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (43)

Moreover, from (16) it is that
$g_{k}\geq\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}\geq 0$, which yields:

$\mathop{\min}\limits_{t=0,\ldots,k-1}{\left\|{\nabla
f({x_{t}})}\right\|^{2}}=o\left({\frac{\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}}\right)\quad
a.s.$ (44)

∎

##  4 Discussion on the UMSLR Stochasticity Factor

Figure 1: Plots that illustrate two SFs for the UMSLR scheme considered. Plot
(a) shows an SF with support $[0.8^{1/k},1.2^{1/k}]$ and plot (b) a close-up
of an SF with support $[0.9^{1/k},1.1^{1/k}]$, where $k$ is the iteration
count.

As mentioned in Section 2, SF distributions for which Assumption 3 holds are
able to be constructed. One such SF distribution is the uniform distribution
and in particular when the SF is taken to follow
$u_{k}=\mathcal{U}\left(\sqrt[k+1]{c_{1}},\sqrt[k+1]{c_{2}}\right)$ with
$c_{1}>0$. This SF distribution will be used for the empirical results of this
paper. The SF for some hyperparameter values is shown in Fig. 1. An MSLR
scheme which uses a uniformly distributed SF will be referred to as UMSLR. In
this work, UMSLR will refer to the aforementioned $u_{k}$. For the UMSLR
scheme Assumption 3 holds for a wide range of the hyperparameters
$c_{1},c_{2}$ rendering this assumption nonrestrictive in practice, as
Proposition 1 shows.

######  Proposition 1.

Let $u_{k}\sim\mathcal{U}\left(\sqrt[k+1]{c_{1}},\sqrt[k+1]{c_{2}}\right)$
with $0<c_{1}<c_{2}$. Then $\mathbb{E}_{u}[u_{k}]$ is monotone for all $k\geq
0$ for either (a): $c_{1}\geq 1$ and $c_{2}>1$, or (b): $c_{1}<1$ and
$c_{2}\leq 1$, or (c): $0<c_{1}<1$ and $c_{2}=e^{W(-c_{1}lnc_{1})}$ , or (d):
$0<c_{1}<1$ and $\frac{1}{c_{1}}<c_{2}$, where $W$ denotes the principal
branch of the Lambert-W function.

###### Proof.

The expectation of UMSLR with respect to $u$ is
$\mathbb{E}_{u}[u_{k}]=\frac{\sqrt[k+1]{c_{1}}+\sqrt[k+1]{c_{2}}}{2}$. For
ease of notation, we denote $k+1$ as $\bar{k}$. Then the derivative is:

$({\mathbb{E}_{u}}[{u_{k}}])^{\prime}=-\frac{{\sqrt[\bar{k}]{{{c_{1}}}}\ln({c_{1}})+\sqrt[\bar{k}]{{{c_{2}}}}\ln({c_{2}})}}{{{\bar{k}^{2}}}}$
(45)

$Case\,\,(a):c_{1}\geq 1,c_{2}\geq 1.$

If $c_{1}>1$ and $c_{2}\geq 1$ then $\mathbb{E}_{u}[u_{k}]$ is increasing
since if $\bar{k}_{1}\leq\bar{k}_{2}$ then
$\mathbb{E}_{u}[u_{\bar{k}_{1}}]\leq\mathbb{E}_{u}[u_{\bar{k}_{2}}]$. This is
because $\sqrt[\bar{k}_{1}]{c_{1}}<\sqrt[\bar{k}_{2}]{c_{1}}$ and
$\sqrt[\bar{k}_{1}]{c_{2}}\leq\sqrt[\bar{k}_{2}]{c_{2}}$ therefore
$\frac{\sqrt[\bar{k}_{1}]{c_{1}}+\sqrt[\bar{k}_{1}]{c_{2}}}{2}<\frac{\sqrt[\bar{k}_{2}]{c_{1}}+\sqrt[\bar{k}_{2}]{c_{2}}}{2}$,
or equivalently
$\mathbb{E}_{u}[u_{\bar{k}_{1}}]<\mathbb{E}_{u}[u_{\bar{k}_{2}}]$.

$Case\,\,(b):0<c_{1}<1,c_{2}\leq 1.$

If $c_{1}<1$ and $c_{2}\leq 1$ then $\mathbb{E}_{u}[u_{k}]$ is decreasing
since if $\bar{k}_{1}\leq\bar{k}_{2}$ then
$\mathbb{E}_{u}[u_{\bar{k}_{1}}]\geq\mathbb{E}_{u}[u_{\bar{k}_{2}}]$. This is
because in this case $\sqrt[\bar{k}_{1}]{c_{1}}\geq\sqrt[\bar{k}_{2}]{c_{1}}$
and $\sqrt[\bar{k}_{1}]{c_{2}}>\sqrt[\bar{k}_{2}]{c_{2}}$ therefore
$\frac{\sqrt[\bar{k}_{1}]{c_{1}}+\sqrt[\bar{k}_{1}]{c_{2}}}{2}>\frac{\sqrt[\bar{k}_{2}]{c_{1}}+\sqrt[\bar{k}_{2}]{c_{2}}}{2}$,
or equivalently
$\mathbb{E}_{u}[u_{\bar{k}_{1}}]>\mathbb{E}_{u}[u_{\bar{k}_{2}}]$.

$Case\,\,(c):0<c_{1}<1,c_{2}=e^{W(-c_{1}lnc_{1})}.$

If $c_{2}>1$ and $0<c_{1}<1$ then the derivative of $\mathbb{E}_{u}[u_{k}]$
has a single root at:

$\underline{k}=-\frac{{\ln({c_{2}})-\ln({c_{1}})}}{{\ln\left({-\frac{{\ln({c_{2}})}}{{\ln({c_{1}})}}}\right)}}-1,\quad\underline{k}=0,1,\cdots$

If $\underline{k}=0$ this means that $\mathbb{E}_{u}[u_{k}]$ will be monotone
for all $k\geq 0$, i.e., it will be monotone for the whole duration of the
algorithm. The condition $\underline{k}=0$ is satisfied when
$\frac{{\ln({c_{2}})-\ln({c_{1}})}}{{\ln\left({-\frac{{\ln({c_{2}})}}{{\ln({c_{1}})}}}\right)}}-1=0$,
or equivalently when $c_{1}\ln c_{1}+c_{2}\ln c_{2}=0$ from which it follows
$e^{\ln c_{2}}\ln c_{2}=-c_{1}\ln c_{1}$. This means that $\ln
c_{2}=W(-c_{1}\ln c_{1})$. Then, by utilizing the principal branch of the
Lambert-W function it is that $c_{2}=e^{W(-c_{1}\ln c_{1})}$.

$Case\,\,(d):0<c_{1}<1,\frac{1}{c_{1}}<c_{2}.$

Moreover, the same is true when $\underline{k}<0$. This can happen if
$\underline{k}\leq-1$, that is,
$\frac{{\ln({c_{2}})-\ln({c_{1}})}}{{\ln\left({-\frac{{\ln({c_{2}})}}{{\ln({c_{1}})}}}\right)}}\geq
0$. This means that $\ln({c_{2}})-\ln({c_{1}})>0$, i.e., $c_{2}>c_{1}$ or
equivalently $c_{2}>1>c_{1}$, and
$\ln\left({-\frac{{\ln({c_{2}})}}{{\ln({c_{1}})}}}\right)>0$, i.e.,
$\frac{1}{c_{1}}<c_{2}$. Therefore, $\mathbb{E}_{u}[u_{k}]$ is monotone for
either $c_{1}\geq 1,c_{2}\geq 1$ or $c_{1}\leq 1,c_{2}\leq 1$, or $0<c_{1}<1$
and $1<c_{2}<e^{W(1/e)}$ or $0<c_{1}<1$ and $\frac{1}{c_{1}}<c_{2}$, and thus
the proof. ∎

It is noted that the SF distribution of UMSLR satisfies the required
assumptions of Theorem 1, and in particular case 1.2 This is because the
experiments use the hyperparameter values from case (b) of Proposition 1 i.e.,
$0<c_{1}<c_{2}<1$. These values yield a monotone, and in fact increasing,
$\mathbb{E}_{u}[u_{k}]$. Moreover, for every finite values $c_{1}$ and
$c_{2}$, $\mathbb{E}_{u}[u_{k}]$ has an infimum.

Furthermore, case 1.2 requires increasing $\mathbb{E}_{u}[u_{k}]$, decreasing
$Var_{u}[u_{k}]$, $\mathbb{E}_{u}[u_{k}]<1$ and
$Var_{u}[u_{k}]<\mathbb{E}_{u}[u_{k}]$. The first requirement is satisfied as
aforementioned. The third is satisfied since
$\mathbb{E}_{u}[u_{k}]=(c_{1}^{1/k}+c_{2}^{1/k})/2<1$ for $0<c_{1}<c_{2}<1$.
The fourth since
$Var_{u}[u_{k}]=\frac{(c_{2}^{1/k}-c_{1}^{1/k})^{2}}{12}<\frac{(c_{2}^{1/k}+c_{1}^{1/k})^{2}}{4}=\mathbb{E}_{u}[u_{k}]^{2}<\mathbb{E}_{u}[u_{k}]$
where the first inequality follows from the expression of the variance of a
uniformly distributed, at each $k$, random variable, and the latter inequality
follows because $\mathbb{E}_{u}[u_{k}]<1$. The second is satisfied because for
the variance derivative it holds that $\frac{{\partial
Va{r_{u}}[{u_{k}}]}}{{\partial{u_{k}}}}=-\frac{1}{{6{k^{2}}}}(\sqrt[k]{c_{2}}-\sqrt[k]{c_{1}})(\sqrt[k]{c_{2}}\log(c_{2})-\sqrt[k]{c_{1}}\log(c_{1}))<0$
since for the $c_{1},c_{2}$ values considered, both the parentheses factors
are positive. The first factor is positive when $c_{2}>c_{1}$ and the second
when $\sqrt[k]{c_{2}}\ln c_{2}>\sqrt[k]{c_{1}}\ln c_{1}$ or equivalently
$e^{\ln c_{2}}\ln c_{2}^{1/k}>e^{\ln c_{1}}\ln c_{1}^{1/k}$. Applying the
principal branch of the Lambert W function then gives $\ln
c_{2}^{1/k}>W(c_{1}^{1/k}\ln c_{1}^{1/k})$, which means
$c_{2}>e^{kW(c_{1}^{1/k}\frac{1}{k}\ln c_{1})}=c_{1}$. Therefore, the variance
is decreasing for the hyperparameters $0<c_{1}<c_{2}<1$ used in UMSLR.

Finally, it is verified that UMSLR provides faster a.s. convergence rates for
SGD than a determinisitc learning rate since from the above it is readily
obtained that
$0<\mathbb{E}_{u}[u_{k}](1-\frac{Var_{u}[u_{k}]}{\mathbb{E}_{u}[u_{k}]})<1$
which means $\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}]<1$. This yields that the
UMSLR a.s. convergence rate of
$o\left(\frac{\mathbb{E}_{u}[u_{k}]-Var_{u}[u_{k}]}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}\right)$
is faster than the deterministic-case rate of
$o\left(\frac{1}{{\sum\nolimits_{t=0}^{k-1}{{\eta_{t}}}}}\right)$. This is
demonstrated experimentally in the next section.

##  5 Results

Experimental results using a stochastic learning rate scheme applied to SGD in
the nonconvex and smooth setting and comparisons to the determinisitc-
learning-rate SGD are presented in this section. In specific, the stochastic
learning rate scheme used was UMSLR, i.e., MSLR with an SF described by
$u_{k}\sim\mathcal{U}\left(\sqrt[k+1]{c_{1}},\sqrt[k+1]{c_{2}}\right)$. The
plots depict either training or testing running losses which were produced by
varying the random seed 40 times and then taking the average of the results.
In summary, when the algorithms where equipped with UMSLR they produced
significantly accelerated convergence and overall optimization performance
than when they employed a deterministic learning rate in the nonconvex
setting, as predicted by Theorem 1. The loss function used was the cross-
entropy loss.

In order to compare the results of UMSLR SGD to its deterministic learning
rate counterpart, t-tests were used for all of the plots. Bonferroni
correction with a family-wise error rate of 0.05 was applied to these t-tests
to determine which plots produced statistically significant results. The step
size was taken to be a constant. The network architecture was ResNet18 and the
datasets used were CIFAR-10 and CIFAR-100 (Krizhevsky (2009)). For both
algorithms the hyperparameters, i.e., learning rates, momentums and the UMSLR
SF constants, were chosen via grid search. All experiments were conducted for
20 epochs each.

As depicted in Figs. 2 and 3, the UMSLR scheme demonstrates significantly
enhanced optimization performance compared to a deterministic learning rate.
Figures 2(a) and 3(a) demonstrate accelerated minimization performance for the
training phase as predicted by Theorem 1. Even though, given the nonconvex
setting, the theorem concerns accelerated convergence to a local minimum, for
the experiments conducted convergence was achieved to the global minimum, i.e,
zero, as demonstrated by the plots. Furthermore, in 2(b) and 3(b) the UMSLR
scheme exhibits enhanced testing-phase performance compared to the
deterministic-learning-rate case since it can be observed that the algorithm
with UMSLR achieves both a faster and a lower minimum testing loss than their
deterministic learning-rate versions. All of the aforementioned results were
statistically significant using a family-wise error rate of 0.05. Even though
the experiments were run for 20 epochs each, the plots for the testing losses
for SGD depict the losses up to the point when overfitting begins, for clarity
of presentation (i.e., up to the point when the testing losses reach their
minimum).

Furthermore, even if the purpose of this work is not producing state-of-the-
art testing performance but rather to showcase the viability of stochastic-
learning-rate methods, testing empirical results were included for
completeness to demonstrate the improved testing performance when using a
stochastic learning rate scheme. More specifically, in all of the cases
presented in these plots the algorithm with an MSLR type of learning rate
achieves both a faster and lower minimum testing loss than its deterministic-
learning-rate counterpart, even if the theoretical analysis conducted in
Theorem 1 concerned only the training phase and not the generalization
performance of the MSLR scheme. In-detail analysis, both theoretical and
experimental, of the testing performance for stochastic-learning-rate
algorithms is left as an avenue for future work.

(a)

(b)

Figure 2: Plots that illustrate the UMSLR scheme (in orange) and the
deterministic learning rate (in blue) schemes applied to SGD under the
nonconvex setting for CIFAR-10 and hyperparameters $c_{1}=0.3$ and
$c_{2}=0.8$.

(a)

(b)

Figure 3: Plots that illustrate the UMSLR scheme (in orange) and the
deterministic learning rate (in blue) schemes applied to SGD under the
nonconvex setting for CIFAR-100 and hyperparameters $c_{1}=0.6$ and
$c_{2}=0.9$.

##  6 Conclusion and Future Work

This work introduced a learning-rate scheme that makes the learning rate
stochastic by multiplicatively equipping it with a random variable, coined
stochastic factor. Almost sure convergence rates of the SGD algorithm in the
nonconvex and smooth setting employing the stochastic learning rate scheme was
theoretically analyzed. The theoretical discussion that followed suggested how
the hyperparameter values introduced by the stochastic-learning-rate scheme
should be chosen. Empirical results on popular datasets demonstrated
noticeable increase in optimization performance, presenting stochastic-
learning-rate schemes as a viable option for enhancing performance. Gains in
testing performance were also observed. In-depth generalization performance
studies, convergence analysis of algorithms besides SHB and SGD, and
investigating the effect of various stochastic factor distributions and
hyperparameters on algorithm performance are some paths for future work.

## References

  * Bertsekas and Tsitsiklis [2000] D. Bertsekas and J. Tsitsiklis.  Gradient convergence in gradient methods with errors.  _SIAM Journal on Optimization_ , 10(3):627–642, 2000.  ISSN 1052-6234.  doi: 10.1137/S1052623497331063.
  * Bottou [2003] L. Bottou.  Stochastic learning.  In _Advances Lectures on Machine Learning_ , volume 3176, 2003.  doi: https://doi.org/10.1007/978-3-540-28650-9_7.
  * Bottou et al. [2018] L. Bottou et al.  Optimization methods for large-scale machine learning.  _SIAM Review_ , 60(2):223–311, jan 2018.  doi: 10.1137/16m1080173.
  * Duchi et al. [2011] J. Duchi et al.  Adaptive subgradient methods for online learning and stochastic optimization.  _J. Mach. Learn. Res._ , 12:2121–2159, July 2011.  ISSN 1532-4435.
  * Khaled and Richtárik [2020] A. Khaled and P. Richtárik.  Better theory for sgd in the nonconvex world, 2020.
  * Kingma and Ba [2015] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In _ICLR (Poster)_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Krizhevsky [2009] A. Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * Loizou and Richtárik [2018] N. Loizou and P. Richtárik.  Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods, 2018.
  * Loizou et al. [2021] N. Loizou et al.  Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence, 2021.
  * Loshchilov and Hutter [2019] I. Loshchilov and F. Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=Bkg6RiCqY7.
  * Mamalis et al. [2021] T. Mamalis et al.  Optimization in the stochastic approximation and online learning settings using stochastic learning rates, 2021.
  * McMahan and Streeter [2010] H. B. McMahan and M. J. Streeter.  Adaptive bound optimization for online convex optimization.  _CoRR_ , abs/1002.4908, 2010.  URL http://dblp.uni-trier.de/db/journals/corr/corr1002.html#abs-1002-4908.
  * Mertikopoulos et al. [2020] P. Mertikopoulos et al.  On the almost sure convergence of stochastic gradient descent in non-convex problems, 2020.
  * Moulines and Bach [2011] E. Moulines and F. Bach.  Non-asymptotic analysis of stochastic approximation algorithms for machine learning.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24. Curran Associates, Inc., 2011.  URL https://proceedings.neurips.cc/paper/2011/file/40008b9a5380fcacce3976bf7c08af5b-Paper.pdf.
  * Nemirovski et al. [2009] A. Nemirovski et al.  Robust stochastic approximation approach to stochastic programming.  _SIAM J. on Optimization_ , 19(4):1574–1609, Jan. 2009.  ISSN 1052-6234.  doi: 10.1137/070704277.  URL https://doi.org/10.1137/070704277.
  * Nguyen et al. [2018] L. Nguyen et al.  SGD and hogwild! Convergence without the bounded gradients assumption.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3750–3758. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/nguyen18c.html.
  * Nocedal and Wright [2006] J. Nocedal and S. J. Wright.  _Numerical optimization_.  New York: Springer, 2006.
  * Polyak [1987] B. T. Polyak.  _Optimization Software_.  Introduction to optimization. translations series in mathematics and engineering. 1987.
  * Reddi et al. [2018] S. J. Reddi et al.  On the convergence of adam and beyond.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=ryQu7f-RZ.
  * Robbins and Monro [1951] H. Robbins and S. Monro.  A stochastic approximation method.  _Ann. Math. Statist._ , 22(3):400–407, 09 1951\.  doi: 10.1214/aoms/1177729586.  URL https://doi.org/10.1214/aoms/1177729586.
  * Robbins and Siegmund [1971] H. Robbins and D. Siegmund.  A convergence theorem for non negative almost supermartingales and some applications**research supported by nih grant 5-r01-gm-16895-03 and onr grant n00014-67-a-0108-0018.  In J. S. Rustagi, editor, _Optimizing Methods in Statistics_ , pages 233–257. Academic Press, 1971.  ISBN 978-0-12-604550-5.  doi: https://doi.org/10.1016/B978-0-12-604550-5.50015-8.  URL https://www.sciencedirect.com/science/article/pii/B9780126045505500158.
  * Sebbouh et al. [2021] O. Sebbouh et al.  Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball, 2021.
  * Zhou et al. [2017] Z. Zhou et al.  Stochastic mirror descent in variationally coherent optimization problems.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper/2017/file/e6ba70fc093b4ce912d769ede1ceeba8-Paper.pdf.