††thanks<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Micromagnets dramatically enhance effects of viscous hydrodynamic flow in
two-dimensional electron fluid

Jack N. Engdahl  School of Physics, University of New South Wales, Sydney
2052, Australia  Aydın Cem Keser  School of Physics, University of New South
Wales, Sydney 2052, Australia  Oleg P. Sushkov  School of Physics, University
of New South Wales, Sydney 2052, Australia

###### Abstract

The hydrodynamic behavior of electron fluids in a certain range of
temperatures and densities is well established in graphene and in 2D
semiconductor heterostructures. The hydrodynamic regime is intrinsically based
on electron-electron interactions, and therefore it provides a unique
opportunity to study electron correlations. Unfortunately, in simple
longitudinal resistance measurements, the relative contribution of
hydrodynamic effects to transport is rather small, especially at higher
temperatures. Viscous hydrodynamic effects are masked by impurities,
interaction with phonons, uncontrolled boundaries and ballistic effects. This
essentially limits the accuracy of measurements of electron viscosity.
Fundamentally, what causes viscous friction in the electron fluid is the
property of the flow called vorticity. In this paper, we propose to use
micromagnets to increase the vorticity by orders of magnitude. Experimental
realization of this proposal will bring electron hydrodynamics to a
qualitatively new precision level, as well as opening a new way to
characterize and externally control the electron fluid.

##  I Introduction

Viscous hydrodynamic flow of the electron fluid, first postulated by Gurzhi
over half a century ago,[1] is now well established experimentally. [2] In the
hydrodynamic regime, the momentum conserving electron-electron scattering
timescale is much shorter than the momentum relaxation timescale related to
impurities and phonons, allowing neighboring electrons to establish local
thermal equilibrium such that the flow behaves as a fluid. This condition
requires samples of very high purity, therefore the theoretical predictions of
the hydrodynamic regime in the 1960s [1, 3] could only be realized
experimentally after the advent of high mobility semiconductors [4] and
graphene. [5, 2] The opposite side of the story is that the relative
contribution of viscous hydrodynamic effects to transport is bounded even in
modern high mobility samples, which drastically limit the precision of all the
existing measurements of viscosity. In this work, we propose a way to overcome
this limitation.

The hydrodynamic nature of the electron flow manifests itself in a number of
phenomena that have been demonstrated in recent studies. While the
hydrodynamic regime was first thought to be experimentally realized in 1995 in
Ref.[4], this interpretation of the results was challenged in the same year in
Ref.[6], as the requirements for viscous hydrodynamics in a two-dimensional
material differs from that in three-dimensions. Reliable evidence of the
hydrodynamic regime was first presented two decades later in Refs.[7, 8, 9].
Notable consequences of hydrodynamic behavior are: the decrease of resistance
with increasing temperature known as the Gurzhi effect,[4, 10, 11, 12, 13, 14]
Poiseuille flow profiles, [15, 16, 17] negative non-local resistance and
formation of whirlpools, [18, 19, 7, 20] Hall viscosity, [13, 21] negative
magnetoresistance, [22, 23, 12, 24, 9, 25] the violation of the Wiedemann-
Franz law, [26, 27, 28, 29, 30] anomalous scaling of resistance with channel
width, [27, 8], resonant photoresistance in magnetic field [31, 32, 33, 34,
25] and quantum-critical dynamic conductivity. [35] Furthermore, many novel
phenomena have been proposed, including the elimination of Landauer-Sharvin
resistance, [36] anisotropic fluids, [37, 38] dynamo effect in the electron-
hole plasma [39] and most excitingly the prospect of hydrodynamic spin
transport [40, 41, 42] inspired by experiments on liquid mercury. [43, 44] So
far almost all experiments in the field have been aimed at a qualitative
demonstration of various hydrodynamic effects. Extraction of quantitative
information has been hindered by the weakness of the contribution of
hydrodynamics effects to electron transport. The quantitative information is
important for understanding correlation effects and it is essential for future
technological applications of the electron fluid.

Figure 1: a) Resistivity of the GaAs device from Ref. [12] versus temperature.
The red line represents the ohmic resistance and the blue line represents the
total (ohmic plus viscous) resistance. b) The map of the viscous dissipation
(proportional to vorticity) in the device (drawn to scale). Vorticity is
concentrated around sharp corners and practically absent in the bulk.

In the hydrodynamic regime, the flow of electrons is characterized by the
viscosity of the electron fluid. Hydrodynamic flow of electrons may be
analyzed using the methods of classical fluid mechanics, particularly solving
the Navier-Stokes equations. [45] While the flow is classical, the viscosity
of the electron fluid is determined by electron-electron scattering that is
purely quantum mechanical. Therefore, precise measurements of viscosity
provides a new way to study electron-electron correlations. [46] The most
precise measurements of the viscosity of electron fluid in 2D GaAs
heterostructure [12] to date indicate deviations from predictions of RPA and
improved RPA Hubbard theory (See also Ref. [25, 46]). To study this deviation
from theory and fully characterize and control the electron fluid, one needs
an effective and precise method to measure viscosity.

To explain the limitations of the existing viscosity measurements in Fig. 1 we
copy two figures from Ref. [12]. Simply, the red line in Fig. 1a approximately
represents the ohmic resistance (scattering from impurities and phonons) and
the blue line represents the total (ohmic plus viscous) resistance. At low
temperatures, $T\lesssim 20-25$K the difference between the ohmic and total
resistance is significant, but this is a manifestation of the transition from
the ballistic to the hydrodynamic regime. The transition itself is an
interesting problem, see Ref. [11], but it is not directly relevant to the
hydrodynamic regime, which is realized at $T\gtrsim 20-25$K in this sample. In
the hydrodynamic regime in this sample, the electron-electron scattering
length is $l_{ee}\sim 100$ nm and the impurity-phonon scattering length is
$l_{imp/ph}\gtrsim 5\>\mu$m. While the hydrodynamic regime is realised as
$l_{ee}\ll l_{imp/ph}$, according to Fig. 1a, the relative contribution of the
viscous dissipation is approximately 10% of the ohmic contribution, a
relatively small contribution. The suppression is easy to understand: the
ohmic dissipation exists throughout the sample, while the viscous dissipation
comes only from the region near the boundaries [45, 47, 48] that contain non-
zero vorticity. This vorticity is generated by obstacles, [49, 50]
inhomogeneities in the geometry [51, 12] or rough channel walls. [15] Boundary
layers have width $\sim D=\sqrt{l_{ee}l_{imp/ph}/4}$ and constitute a small
fraction of the total volume, as shown in Fig. 1b. While this example is
specific to the experiment in Ref. [12], to the best of our knowledge the
issue of the low vorticity is relevant to all existing measurements in
graphene and in semiconductors.

The idea of the present work is to create an oscillatory flow pattern, or
“zigzag” flow, schematically shown in

Figure 2: Velocity field $\mathbf{v}$ (arrows) and streamlines (solid black
lines) in a) the “zigzag” flow versus b) in ordinary flow inside a no-slip
channel, where tangential velocity is zero at the boundaries. In (b) the
velocity is purely horizontal and is uniform in the bulk, but the magnitude
decays to zero near the no-slip boundaries, forming a non-uniform profile (red
dashed lines). Therefore, the strength of vorticity
$|\hat{z}\cdot\nabla\times\mathbf{v}|$ (normalized and shown by pink shade) is
distributed throughout the bulk in (a), whereas in (b) it is exponentially
small except in the boundary layers.

Fig. 2. In the flow through a channel with non-uniform or rough boundaries, a
profile develops that is schematically illustrated by the dashed red lines
shown in Fig. 2. In such a conventional flow, vorticity is limited to regions
near the boundaries of the channel. On the contrary, the solid black
oscillatory streamlines in Fig. 2 carry a uniform vorticity throughout the
bulk area, and hence the viscous dissipation can match or exceed the ohmic
dissipation.

Periodic geometric modulation or obstacles, create boundary layers near
geometric features which decay into the bulk [49, 12] (see for example red
regions in Fig. 1b). Therefore, the “zigzag” flow in the bulk cannot be
established through geometric modulation. However, this non-decaying “zigzag”
flow profile may be generated using micromagnets that produce a spatially non-
uniform magnetic field of amplitude in the range $20$-$30$ mT, that permeates
the bulk. The spatial period of the magnetic field must be of the order of a
few $\mu$m, similar to the characteristic viscous length scale. In principle,
the idea of the oscillatory flow is equally applicable to the two-dimensional
electron gas (2DEG) in both semiconductor quantum wells and graphene. However,
boundary conditions that reconcile the oscillatory flow with flat boundaries
are significantly different for these two cases. In this paper, we consider
the semiconductor 2DEG in a straight channel with no-stress boundary
condition.

The structure of the paper is as follows. In Section II we solve the Stokes
equation exactly for an infinitely wide 2D flow channel with a sinusoidally
modulated perpendicular magnetic field. The direction of modulation coincides
with the direction of the flow. This allows us to calculate the viscous and
the ohmic dissipation rates and to show that the ratio of viscous to ohmic
dissipation can be tuned to become large. Any realistic flow channel has a
finite width, therefore in Section III we study the boundary layer in a
straight channel using the no-stress boundary condition. Through this solution
we find the flow inside the boundary layer. Since the boundary layer problem
is the most mathematically delicate issue, we solve the problem by two
different methods, (i) perturbation theory, (ii) exact numerical solution. The
central result of Section III is the width of the boundary layer. This proves
that the “zigzag” flow can be realized in a sufficiently wide straight channel
and allows the determination of an appropriate channel width. In Section IV we
calculate the magnetic field of periodic ferromagnetic stripes and hence
determine parameters of micromagnets necessary for the experimental set up.
Section V presents our conclusions.

##  II Flow in infinitely wide and infinitely long 2D channel

We consider low currents in the 2DEG, corresponding to low Reynolds number
flow. Therefore, we will neglect the Navier term,
$\mathbf{v}\cdot\nabla\mathbf{v}$, in the Navier-Stokes equation as it is
quadratic in velocity. The flow is also incompressible as the charge carrier
density in the 2DEG is controlled via the top gate voltage. Furthermore, we
assume steady flow has been established in the channel. The resulting
stationary Stokes equation for a two-dimensional incompressible electron fluid
in a magnetic field reads [45]

$\displaystyle\mathbf{v}/\tau-\nu\nabla^{2}\mathbf{v}$
$\displaystyle=-\nabla\Phi/m^{*}+q/m^{*}\mathbf{v}\times\mathbf{B},$
$\displaystyle\nabla\cdot\mathbf{v}$ $\displaystyle=0.$ (1)

Here $\mathbf{v}$ is the fluid velocity, $\nu$ is the kinematic viscosity,
$\tau$ is the relaxation time related to ohmic processes (scattering from
impurities and phonons), $\Phi$ is the electro-chemical potential, $q$ is the
charge of the fluid particle, $m^{*}$ is the effective hydrodynamic mass and
$\mathbf{B}$ is the magnetic field. The magnetic field perpendicular to the
plane of the 2DEG is periodically modulated along the flow as

$\displaystyle B=B_{z}$ $\displaystyle=B_{0}b(x),$ $\displaystyle b(x)$
$\displaystyle=\sin(gx),$ $\displaystyle g$ $\displaystyle=\frac{2\pi}{a}.$
(2)

For electrons in GaAs, considered in the present paper, the mass $m^{*}$ is
just the band structure mass, $m^{*}\approx 0.067m_{e}$. Using the no-stress
boundary condition method developed in Ref.[12] the relaxation time $\tau$ can
be measured independently of hydrodynamics. $\tau$ is a known phenomenological
function of temperature. It is convenient to relate the viscosity and the
relaxation time to the electron-electron scattering length $l_{ee}$ and to the
electron mean free path $l_{mfp}$.

$\displaystyle\nu$ $\displaystyle=\frac{1}{4}v_{F}l_{ee},$ $\displaystyle\tau$
$\displaystyle=\frac{l_{mfp}}{v_{F}}.$ (3)

The relations (II) are well known at low temperatures, $T\ll\epsilon_{F}$,
where $\epsilon_{F}$ is the Fermi energy. We extend (II) to higher
temperatures, $T\sim\epsilon_{F}$, using these relations as definitions of the
corresponding lengths, where we use the Fermi velocity $v_{F}$ defined at zero
temperature,

$\displaystyle v_{F}=\frac{p_{F}}{m^{*}}=\frac{\sqrt{2\pi n}}{m^{*}}.$ (4)

Here $n$ is the number density of the 2DEG and $p_{F}$ is the Fermi momentum.

The viscosity depends on magnetic field [9] as,

$\displaystyle\nu\propto\frac{1}{1+(B/B^{*})^{2}}.$ (5)

Here, $B^{*}$ is the characteristic magnetic field of the material, related to
the electron-electron scattering length by $B^{*}={p_{F}}/{(2|e|l_{ee})}$. [9]
Although this suppression of viscosity by the magnetic field can be
incorporated in our analysis, we consider very weak fields, $B\sim B^{*}/10$,
so we disregard the $B$-dependence of $\nu$.

To solve Eq. (II) it is convenient to use the stream function, $\psi$, defined
as

$\displaystyle v_{x}$ $\displaystyle=\partial_{y}\psi,$ $\displaystyle v_{y}$
$\displaystyle=-\partial_{x}\psi,$ (6)

which ensures that $\nabla\cdot\mathbf{v}=0$. Acting on Eq (II) with the curl
operator $\nabla\times$, and using the definition Eq. (II), we obtain

$\displaystyle-\nabla^{2}\psi+D^{2}\nabla^{4}\psi$
$\displaystyle=\omega\tau(\partial_{x}b)\partial_{y}\psi,$ (7a)
$\displaystyle\omega=\frac{|q|B_{0}}{m^{*}},$ $\displaystyle\quad
D=\sqrt{\nu\tau}=\frac{1}{2}\sqrt{l_{ee}l_{mfp}}.$ (7b)

We first consider an applied current density $\mathbf{J}=qnv_{0}\hat{x}$ that
passes through a very large system and find

$\psi_{\infty}=v_{0}\left(y+\frac{\omega\tau}{g(1+D^{2}g^{2})}\cos(gx)\right),$
(8)

where the subscript $\infty$ indicates that this is the solution when system
width and length tend to infinity. Indeed, the stream function in Eq. 8
generates the zigzag flow shown in Fig. 2. Note that if the magnetic field has
many Fourier components,
$b(x)=\sum_{n=1}^{\infty}[\alpha_{n}\sin(ngx)+\beta_{n}\cos(ngx)]$, the
generalization of Eq. (8) is straightforward.

Instead of determining the relationship between electrochemical potential and
current from Eq. (II), we can infer the resistance in the system by accounting
for the total power dissipation. The terms $m^{*}\mathbf{v}/\tau$ and
$-m^{*}\nu\nabla^{2}\mathbf{v}$ in Eq. (II) are respectively the ohmic drag
and viscous friction forces in the system. Therefore, the force velocity
product gives the corresponding dissipation rates which follow from Eqs. (II)
and (8) as

$\displaystyle\frac{\dot{E}_{\Omega}}{LW}=\frac{nm^{*}}{LW\tau}\int
d^{2}rv^{2}=\frac{nm^{*}v_{0}^{2}}{\tau}\
\left(1+\frac{\omega^{2}\tau^{2}}{2(1+D^{2}g^{2})^{2}}\right),$
$\displaystyle\frac{\dot{E}_{\nu}}{LW}=\frac{-nm^{*}\nu}{LW}\int
d^{2}r{\bm{v}}\cdot\nabla^{2}{\bm{v}}=\frac{nm^{*}v_{0}^{2}}{2\tau}\
\left(\frac{gD\omega\tau}{1+D^{2}g^{2}}\right)^{2}.$ (9)

Here $L$ and $W$ are the length and the width of the channel respectively.

We may tune free parameters to maximize the ratio
$\dot{E}_{\nu}/\dot{E}_{\Omega}$ such that viscous transport is not
overshadowed by ohmic effects. It is easy to check that at a fixed value of
$\omega\tau$ the ratio is maximum at the following value of $gD$

$\displaystyle t=\omega\tau,$ $\displaystyle gD=[1+t^{2}/2]^{1/4},$
$\displaystyle
R=\frac{\dot{E}_{\nu}}{\dot{E}_{\Omega}}=\frac{t^{2}}{4(1+\sqrt{1+t^{2}/2})}.$
(10)

At large magnetic field the ratio grows linearly with amplitude of the
magnetic field, $R\approx\omega\tau/(2\sqrt{2})$. However, to avoid the
influence of the magnetic field on the viscosity, Eq. (5), we need $B_{0}\ll
B^{*}$. This means that the optimization of parameters depends on the value of
the relaxation time $\tau$ that is related to the mobility of the 2DEG.

We make realistic estimates for the effect of periodic magnetic field on the
GaAs system from Ref. [12]. In order to pick the optimum value for the period
of the magnetic superlattice, we first determine $\omega\tau$ from the
experimentally measured parameters of the 2DEG. At $T=30-40$K and density
$n\sim few\times 10^{11}\>\text{cm}^{-2}$ has $B^{*}\approx 200-250$mT,
$\tau\approx 0.3\times 10^{-10}$s and the corresponding mean free path
$l_{mfp}\approx 7\mu$m. If we take $B_{0}=30$ mT the $B^{*}$ correction in Eq.
(5) to $\nu$ at the peak magnetic field strength is approximately 2% and can
be safely neglected. With these values of $B_{0}$ and $\tau$ we find
$\omega\tau=2.4$ and hence according to Eq. (II) the ratio is $R\approx 0.5$.
Hence, we achieve almost an order of magnitude enhancement of the viscous
dissipation compared to Fig. 1a. The value of the characteristic length $D$
defined in Eq. (7a) is $D\approx 0.6\mu$m. Finally, according to Eq. (II) the
optimal period of the magnetic superlattice is $a=2\pi/g\approx 2.6\>\mu$m.

##  III Boundary layer for a straight channel with no-stress boundary
condition

In the previous section we considered an infinite fluid domain. Of course, any
physical channel must have some finite width $W$. Here we consider a straight
channel with no-stress boundary conditions engineered experimentally in Ref.
[12]. To support the message of the previous section, we seek to prove that
the boundary layer that reconciles the oscillatory bulk flow with the straight
flow near the boundary is of a finite width. In other words, the width of the
boundary layer must remain finite as the amplitude of magnetic field is
increased. Because of the importance of this assertion, we check it by two
different methods, (i) analytic solution using perturbation theory in magnetic
field, and (ii) exact numerical solution.

###  III.1 Perturbation theory for the boundary layer flow

For the purpose of deriving an analytic expression for the boundary, we
consider the boundary region as a semi-infinite channel with domain $y>0$ and
a perfect-slip boundary at $y=0$. Together with the Stokes equation, Eq. (7a),
the stream function must satisfy the no-penetration and perfect-slip, or no-
stress, boundary conditions as follows, respectively,

$v_{y}|_{y=0}=-\partial_{x}\psi|_{y=0}=0,\;\partial_{y}v_{x}|_{y=0}=\partial_{y}^{2}\psi|_{y=0}=0.$
(11)

The former, no-penetration condition ensures no fluid can enter/exist through
the boundary. Whereas the latter no-stress condition ensures that the fluid
experiences no friction from the boundary, in other words the perfect-slip
condition is realized. Furthermore, the stream function must decay to the bulk
solution (8) far from the boundary. We look for a solution as an expansion in
the powers of $\omega\tau\ll 1$,
$\psi=\sum_{n=0}^{\infty}(\omega\tau)^{n}\psi^{(n)}$. Straightforward
substitution in Eqs. (7a),and (11) gives the following 1st order solution

$\displaystyle\psi$ $\displaystyle=$ $\displaystyle
v_{0}\left\\{\left(y+\frac{\omega\tau}{g(1+g^{2}D^{2})}\cos(gx)\right)\right.$
$\displaystyle+$
$\displaystyle\left.\frac{\omega\tau}{g}\left(\frac{g^{2}D^{2}}{1+g^{2}D^{2}}e^{-\sqrt{g^{2}D^{2}+1}y/D}-e^{-gy}\right)\cos(gx)\right\\}.$

Due to the optimization condition (II) the wave vector is $g>1/D$, therefore
the boundary layer part of the solution (III.1) decays faster than the
characteristic length $D$. In Appendix A we present the expansion of the
solution to $\psi$ to the second order in $\omega\tau$ to demonstrate that the
effective width of higher order contributions to the boundary decreases with
increasing order. The corrections to $\psi$ to second order in $\omega\tau$
part has boundary layer terms that exponentially decay with $y$ at the same
rate as that in Eq. (III.1) or faster. Fig. 3 presents plots of streamlines
obtained in the 1st and the 2nd order perturbation theory at
$\omega\tau=0.5,1$ and $gD=1$.

Figure 3: Streamlines for $gD=1$ and $\omega\tau=0.5$ (left) and
$\omega\tau=1$ (right). Solid lines correspond to the 1st order perturbation
theory and dashed lines correspond to the 2nd order perturbation theory. In
both cases the dashed lines almost exactly coincide with the solid lines for
$y>D$.

The difference between the solid and the dashed lines in Fig. 3 characterize
the convergence of the perturbation theory. While at $\omega\tau=0.5$ there is
practically no visible difference between the first and second order
perturbation theory, the difference is visible when $\omega\tau=1$. In both
cases the boundary layer has almost entirely decayed for $y>2D$, with the flow
indistinguishable from the bulk solution given by Eq. (8).

The perturbation theory at $\omega\tau=1$ does not satisfy the small
$\omega\tau$ limit and it is hardly possible to justify the perturbation
theory at $\omega\tau\approx 3$ corresponding to the optimal device.
Therefore, in the following subsection we present the numerical solution valid
at arbitrary $\omega\tau$.

###  III.2 Exact numerical solution for the boundary layer flow

Figure 4: Streamlines in a channel with no-stress boundaries with width
$W=14D$. The parameters of the magnetic field are chosen as $gD=1$,
$\omega\tau=1,3,9$. Solid lines correspond to the numerically exact solution
described in Sec. III.2 and dashed lines correspond to the solution given by
Eq. (8) in the infinite device.

In this section, we reduce the Stokes equation, Eq. (7a), to an infinite
sequence of linear algebraic equations. We then numerically solve these
equations by truncating them at a suitable order. We consider an infinitely
long channel of width $W$ and use length units where $D=\sqrt{\nu\tau}=1$. As
the magnetic field is periodic in the $x$-direction so is the stream function,
$\psi$, which can be presented as the following Fourier series,

$\displaystyle\psi=v_{0}y+v_{0}W\sum_{m=-\infty}^{\infty}e^{igmx}G_{m}(y)\ .$
(13)

Here $G_{m}(y)$ are unknown functions to be determined. The first term
$v_{0}y$ corresponds to the uniform velocity $v_{x}=v_{0}\neq 0,\>v_{y}=0$.

At $y=0$ and, $y=W$ the stream function must satisfy the no-penetration and
no-stress boundary conditions, previously given for $y=0$ in Eq. (11). The no-
penetration condition implies that $G_{m}(0)=G_{m}(W)=0$. Hence, the functions
$G_{m}(y)$ can be expanded in a Fourier series in $\sin\left(ny\pi/W\right)$
as

$\displaystyle\psi/v_{0}=y+W\sum_{n=1}^{\infty}\sum_{m=-\infty}^{\infty}f_{m,n}e^{igmx}\sin\left(\frac{ny\pi}{W}\right),$
(14)

where $f_{m,n}$ are complex coefficients. Note that, this form is chosen so
that the no-stress condition is automatically satisfied. Furthermore, the
sinusoidal terms do not contribute to the average current through the channel.
The Navier-Stoke’s equation, Eq. 7a, expressed in terms of the coefficients
$f_{m,n}$ reads

$\sum_{n=1}D_{m,n}f_{m,n}\sin(ny\pi/W)=\frac{\alpha}{2}\bigg{(}\delta_{m,1}+\delta_{m,-1}\\\
+\sum_{n=1}\left[f_{m+1,n}+f_{m-1,n}\right]n\pi\cos(ny\pi/W)\bigg{)},$ (15)

where $\alpha=-\omega\tau g/W$ and

$D_{m,n}=-\left[\left(mg\right)^{2}+\left(\frac{\pi
n}{W}\right)^{2}\right]\left[\left(mg\right)^{2}+\left(\frac{\pi
n}{W}\right)^{2}+1\right].$ (16)

Eq. (15) is defined only at $0<y<W$. Therefore, one cannot naively equate the
Fourier components. Instead we must integrate over $y$ using the following
identities

$\displaystyle\int_{0}^{1}dy\>\sin(ny\pi)\sin(ly\pi)=\frac{1}{2}\delta_{n,l},$
$\displaystyle\int_{0}^{1}dy\>\cos(ny\pi)\cos(ly\pi)=\frac{1}{2}\delta_{n,l},$
$\displaystyle\int_{0}^{1}dy\>\sin(ny\pi)\cos(ly\pi)=F(n,l),$ $\displaystyle
F(n,l)=\left\\{\begin{array}[]{ccc}0&,&n+l=even\\\
\frac{2n}{\pi(n^{2}-l^{2})}&,&n+l=odd.\end{array}\right.$ (19)

Hence, Eq.( 15) is reduced to the following system of linear algebraic
equations for the coefficients $f_{m,l}$:

$\displaystyle\begin{split}D_{m,l}f_{m,l}={\alpha}&\bigg{(}\sum_{n=1}^{\infty}\left[f_{m+1,n}+f_{m-1,n}\right]n\pi
F(l,n)\\\ &+(\delta_{m,1}+\delta_{m,-1})F(l,0)\bigg{)},\>l>0,\end{split}$
(20a)
$\displaystyle\begin{split}\sum_{n=1}^{\infty}D_{m,n}f_{m,n}&F(n,l)=\frac{\alpha}{4}\bigg{(}\left[f_{m+1,l}+f_{m-1,l}\right]l\pi\\\
&+\left[f_{m+1,n}+f_{m-1,n}\right]\delta_{l,0}\bigg{)},\>l\geq 0.\end{split}$
(20b)

We truncate beyond $|m|,l,n>50$. With a channel width $W=14$ the truncation
implies spatial uncertainty $\sim 14/50\approx 0.3$, which is accurate enough
to describe the boundary layer.

Plots of the streamlines obtained from this numerical solution for $gD=1$ and
$\omega\tau=1,3,9$ are presented in Fig. 4.

Figure 5: The ratio of viscous to ohmic dissipation at $gD=1$. For the
infinite system (solid black line), this ratio is calculated from Eq. (II).
For a system with finite width, $W=7D$ (red dots) and $W=14D$ (blue dots), it
is calculated from the numerical solution in Sec. III.2. Finite width
(boundary layer) effects are negligible when $W\gg 2D$ below
$\omega\tau\lesssim 6$.

The exact solution demonstrates that the width of the boundary layer increases
with increasing magnetic field. For the most interesting case,
$\omega\tau\approx 3$ the width of the boundary layer is about $2D$. The fact
that the boundary layers are growing in size with $\omega\tau$ is also evident
in Fig. 5. We compare the ratio of viscous to ohmic dissipation in an infinite
channel, as calculated in Eq. (II), to a finite width channel. In Fig. 5, the
ratio calculated from the exact solution approaches that of an infinite system
as the channel width grows, as expected. Of course, for small values of
$\omega\tau<1$, the thin boundary layers, as in Fig. 4, have vanishing stress
that reduces viscous dissipation. More interestingly, the finite width
corrections become noticeable at large $\omega\tau$, where the boundary layer
width $2D$ is comparable to the width $W$. Hence, the width of the channel $W$
must be significantly larger than $2D$ for boundary layer effects to be small.
For GaAs with mobility of about $10^{6}$ corresponding to the device from Ref.
[12] this implies that $W\gg 1.2\mu$m.

##  IV Magnetic field of periodic ferromagnetic stripes

The calculations in this section demonstrate that realization of the optimal
magnetic field profile for studies in the hydrodynamic regime is realistically
achievable.

We consider a setup consisting of an array of rectangular magnetic bars
perpendicular to the longitudinal axis of the flow channel, as seen below in
the left panel of Fig. 6.

Figure 6:  Left: top view of a periodic array of magnetic bars perpendicular
to the flow direction shown by the red arrow. The period of the array is $a$
and the width of the bar is $d$. The bars are magnetized parallel to the
longitudinal axis of the channel. The direction of the magnetization is shown
by the blue arrows. Right: Side view of the device. The vertical distance from
the bar magnets to the 2DEG is $z$ and the thickness of the rectangular bar is
$\delta z$.

The bars are magnetized along the longitudinal axis of the channel. The bar
thickness is $\delta z$ and the distance from the base of the bar to the 2DEG
is $z$, shown in the right panel of Fig. 6. We set the value of the period
$a=2.6\mu$m as obtained in Sec. II. We tune the remaining free parameters
$d,z,\delta z$ such that the z-component of magnetic field in the 2DEG is
approximately $B_{0}\sin(2\pi x/a)$ with $B_{0}\approx 30$ mT. This value of
$B_{0}$ limits the magnetic correction to the viscosity to a maximum of
approximately 2% and thus this effect may be safely neglected in the analysis.
Assuming the magnetic moment is uniform throughout the volume of each bar, and
the bars extend in the transverse ($y$) direction wider than the width $W$ of
the sample, we calculate the magnetic field on the plane of 2DEG as a function
of longitudinal coordinate $x$, from the Biot-Savart law as

$\frac{B_{z}(x)}{B_{m}}\bigg{|}_{2DEG}=-\sum_{n>1}\frac{\sin\left(gnd/2\right)}{\pi
n}\sin(gnx)Z_{n},\\\ Z_{n}(z,\delta z)=e^{-gnz}(1-e^{-gn\delta z}),$ (21)

where $B_{m}$ is the saturation field, and $x$ is measured from the center of
one of the magnets. For example, at the edge of the magnet $x=d/2$, the
harmonics of the field on 2DEG plane is $\propto\sin^{2}(gnd/2)$. Therefore,
$d=a/2=\pi/g$ maximizes the first harmonic and suppresses the second harmonic.
We numerically calculate $B$ from Eq (21) and further confirm that
$d=a/2=1.3\>\mu$m is optimal. In other words, matching the width of the magnet
to the spacing between successive magnets creates an effectively sinusoidal
magnetic field profile without higher harmonics.

We consider two magnetic materials, (i) Ni that has saturation magnetic field
600mT [52] and (ii) NiFe alloy that has saturation magnetic field 1500mT. [53]
We consider two values of bar thickness, $\delta z=0.3\>\mu$m and $\delta
z=0.2\>\mu$m. After fixing these values, the only free parameter is the
distance to 2DEG $z$, which we tune.

Figure 7:  Magnetic field in the 2DEG plane for Ni bars. Left panel: $B_{z}$
versus $x$. Right panel: $B_{x}$ versus $x$. The parameter sets are: black
solid line $\delta z=0.2\>\mu\mathrm{m},\ z=0.4\>\mu\mathrm{m}$, red dashed
line $\delta z=0.3\>\mu\mathrm{m},\ z=0.5\>\mu\mathrm{m}$.

Plots of $B_{z}$ versus $x$ for Ni bars for $\delta z=0.2\>\mu\mathrm{m},\
z=0.4\>\mu\mathrm{m}$ and for $\delta z=0.3\>\mu\mathrm{m},\
z=0.5\>\mu\mathrm{m}$ are presented in the left panel of Fig. 7. Fields for
these parameter sets are practically indistinguishable and close to the simple
sinusoidal dependence with amplitude $30$ m T. In the right panel of Fig. 7 we
plot the $x$-component of magnetic field for the same sets of parameters. Of
course the $x$-component does not influence hydrodynamics, but it remains
instructive to see the magnitude and the $x$-dependence.

Plots of $B_{z}$ versus $x$ for NiFe bars for ($\delta z=0.2\>\mu\mathrm{m},\
z=0.75\>\mu\mathrm{m}$) and for ($\delta z=0.3\>\mu\mathrm{m},\
z=0.87\>\mu\mathrm{m}$) are presented in the left panel of Fig. 8. Again,
fields for these parameter sets are practically indistinguishable and closely
follow a sinusoidal pattern as desired. In the right panel of Fig. 8 we plot
the $x$-component of magnetic field for the same sets of parameters.

Figure 8:  Magnetic field in the 2DEG plane for NiFe bars. Left panel: $B_{z}$
versus $x$. Right panel: $B_{x}$ versus x. The parameter sets are: black solid
line $\delta z=0.2\>\mu\mathrm{m},\ z=0.75\>\mu\mathrm{m}$, red dashed line
$\delta z=0.3\mu m,\ z=0.87\>\mu\mathrm{m}$.

##  V Conclusions

In this work we propose a new method to study viscous hydrodynamic flow of
electrons in 2D mesoscopic systems. This method involves the use of
micromagnets to drive oscillatory flow everywhere in the fluid domain,
promoting viscous dissipation not just in the boundary layer but also in the
bulk. The proposed method allows for improved precision of hydrodynamic
measurements by at least an order of magnitude compared to existing state-of-
the-art experiments. With such an improvement in accuracy, electron
hydrodynamics presents itself as a novel and efficient method to study
electron-electron correlations.

##  Acknowledgements

We acknowledge important discussions with Alexander Hamilton, Igor Zutic, Oleh
Klochan and Daisy Wang. This work was supported by the Australian Research
Council Centre of Excellence in Future Low- Energy Electronics Technologies
(CE170100039).

##  Appendix A Perturbative solution of boundary layer to second order

In Sec. III.1 we presented the perturbative boundary layer solution to first
order. This first order solution was derived by solving Eq.(7a) for the stream
function, defined in Eq. (II), to first obtain the driven solution and then
again for a judiciously crafted free solution. The generalized complete first
order solution was then subject to the boundary conditions, Eq.(11), in order
to completely define all coefficients. Now, this process can be repeated ad
infinitum to obtain higher order corrections of the series

$\psi=v_{0}y+v_{0}\sum_{n=1}^{\infty}(\omega\tau)^{n}\psi^{(n)}.$ (22)

Here $\psi^{(n)}$ independently satisfies the boundary conditions Eq. (11) at
each order of correction. For simplicity we write distance in units $D=1$. We
may decompose $\psi^{(n)}$ into free and driven components as we did to first
order in the text

$\psi^{(n)}=\psi_{f}^{(n)}+\psi_{d}^{(n)},\quad(-\nabla^{2}+\nabla^{4})\psi_{f}^{(n)}=0.$
(23)

The free solution must be of the form

$\psi_{f}^{(n)}=\sum_{m=1}^{n}\sum_{s=0,1}A^{(n)}_{m,s}\cos(mgx)e^{-\lambda_{m,s}y},$
(24)

where

$\lambda_{m,s}=\sqrt{m^{2}g^{2}+s},\quad s=0,1.$ (25)

The Stokes operator, $-\nabla^{2}+\nabla^{4}$, becomes invertible when acting
on the driven solution. Therefore the driven solution can be written as

$\psi_{d}^{(n)}=\sum_{\lambda}\sum_{m=1}^{n}B^{(n)}_{m}(\lambda)\cos(mgx)e^{-\lambda
y},$ (26)

where $\lambda$ is chosen from the set of $\lambda_{m^{\prime},s}$ given by
the formula in Eq. (25), defined for the indices $0\leq m^{\prime}<n$ and
$s=0,1$. We also note that, in this choice, the term with
$B_{m}^{(n)}(\lambda_{m,s})$ never appears, as it is part of the homogeneous
solution (i.e. it belongs to the kernel of the Stokes operator).

To first order the Stokes equation, Eq. (7a), reads

$\sum_{\lambda}B^{(1)}_{1}(\lambda)e^{-\lambda
y}(\lambda^{2}-\lambda_{1,0}^{2})(\lambda^{2}-\lambda^{2}_{1,1})=g.$ (27)

This equation is satisfied only for $\lambda=\lambda_{0,0}=0$. Therefore the
only non-vanishing coefficient is

$B^{(1)}_{1}(\lambda_{0,0})=\frac{g}{\lambda_{1,0}^{2}\lambda^{2}_{1,1}}=\frac{1}{g(g^{2}+1)}.$
(28)

The remaining two coefficients, $A^{(1)}_{1,s}$ where $s=0,1$, may be
determined from the boundary conditions, Eq. (11).

$\displaystyle\sum_{s=0,1}A^{(1)}_{1,s}+B_{1}^{(1)}(\lambda_{0,0})$
$\displaystyle=$ $\displaystyle 0,$ (29)
$\displaystyle\sum_{s=0,1}A^{(1)}_{1,s}\lambda_{1,s}^{2}$ $\displaystyle=$
$\displaystyle 0.$ (30)

The solutions are $A^{(1)}_{1,s}=-g(-1)^{s}\lambda_{1,s}^{-2}$ where $s=0,1$,
or explicitly

$\displaystyle A_{1,0}^{(1)}$ $\displaystyle=$
$\displaystyle-\frac{g}{\lambda_{1,0}^{2}}=-\frac{1}{g},$ (31) $\displaystyle
A_{1,1}^{(1)}$ $\displaystyle=$
$\displaystyle\frac{g}{\lambda_{1,1}^{2}}=\frac{g}{g^{2}+1}.$ (32)

The first order solution is completely defined by the coefficients
$A^{(1)}_{1,0},A^{(1)}_{1,1}$ and $B^{(1)}_{1}(\lambda_{0,0})$, written
explicitly as Eq. (III.1) in the main text.

The first order solution, $\psi^{(1)}$, acts as a source for the second order
driven solution, $\psi_{d}^{(2)}$. By solving the Stokes equation, Eq. (7a),
we find the non-vanishing coefficients of $\psi_{d}^{(2)}$ to be

$B_{m}^{(2)}(\lambda_{1,s})=\frac{(-1)^{s}g^{2}}{2\lambda_{1,s}(\lambda_{1,s}^{2}-\lambda_{m,0}^{2})(\lambda_{1,s}^{2}-\lambda_{m,1}^{2})},\\\
\mathrm{for}\quad m=0,2,\>s=0,1.$ (33)

To satisfy the boundary conditions, Eq. (11), the second order free solution
has non-vanishing coefficients $A^{(2)}_{m,s}$ for $m=0,2$ and $s=0,1$. The
coefficient $A^{(2)}_{0,0}$ precedes a constant term and thus its value does
not affect the current and voltage distribution. The boundary conditions
provide three equations for the remaining three coefficients. Setting
$A^{(2)}_{0,0}$ appropriately, we have

$A_{m,r}^{(2)}=\frac{g^{2}}{2}\sum_{s=0,1}\frac{(-1)^{r+s}}{\lambda_{1,s}(\lambda_{1,s}^{2}-\lambda_{m,r}^{2})},\\\
\mathrm{for}\quad m=0,2,\>r=0,1.$ (34)

Evidently, the leading term of the second order correction decays at a faster
rate than that of the first order correction. Higher order boundary layers
decay at a rate faster than that of $\exp(-gy)$ or $\exp(-y/D)$. Thus in the
perturbative regime, $\omega\tau<1$, the width of the boundary layer is finite
with an effective width comparable to the largest of $D$ and $1/g$.

## References

  * Gurzhi [1968] R. N. Gurzhi, Hydrodynamic effects in solids at low temperature, Soviet Physics Uspekhi 11, 255 (1968), publisher: IOP Publishing.
  * Polini and Geim [2020] M. Polini and A. K. Geim, Viscous electron fluids, Physics Today 73, 28 (2020).
  * Gurzhi [1963] R. N. Gurzhi, Minimum of Resistance in Impurity-free Conductors, JETP 17, 521 (1963).
  * de Jong and Molenkamp [1995] M. J. M. de Jong and L. W. Molenkamp, Hydrodynamic electron flow in high-mobility wires, Phys. Rev. B 51, 13389 (1995), publisher: American Physical Society.
  * Lucas and Fong [2018] A. Lucas and K. C. Fong, Hydrodynamics of electrons in graphene, Journal of Physics: Condensed Matter 30, 053001 (2018), publisher: IOP Publishing.
  * Gurzhi  _et al._ [1995] R. N. Gurzhi, A. N. Kalinenko, and A. I. Kopeliovich, Electron-Electron Collisions and a New Hydrodynamic Effect in Two-Dimensional Electron Gas, Physical Review Letters 74, 3872 (1995).
  * Bandurin  _et al._ [2016] D. A. Bandurin, I. Torre, R. K. Kumar, M. Ben Shalom, A. Tomadin, A. Principi, G. H. Auton, E. Khestanova, K. S. Novoselov, I. V. Grigorieva, L. A. Ponomarenko, A. K. Geim, and M. Polini, Negative local resistance caused by viscous electron backflow in graphene, Science 351, 1055 (2016), publisher: American Association for the Advancement of Science.
  * Moll  _et al._ [2016] P. J. W. Moll, P. Kushwaha, N. Nandi, B. Schmidt, and A. P. Mackenzie, Evidence for hydrodynamic electron flow in $\mathrmPdCoO_2$, Science 351, 1061 (2016), publisher: American Association for the Advancement of Science.
  * Alekseev [2016] P. S. Alekseev, Negative Magnetoresistance in Viscous Flow of Two-Dimensional Electrons, Phys. Rev. Lett. 117, 166601 (2016), publisher: American Physical Society.
  * Krishna Kumar  _et al._ [2017] R. Krishna Kumar, D. A. Bandurin, F. M. D. Pellegrino, Y. Cao, A. Principi, H. Guo, G. H. Auton, M. Ben Shalom, L. A. Ponomarenko, G. Falkovich, K. Watanabe, T. Taniguchi, I. V. Grigorieva, L. S. Levitov, M. Polini, and A. K. Geim, Superballistic flow of viscous electron fluid through graphene constrictions, Nature Physics 13, 1182 (2017), iSBN: 1745-2481.
  * Bandurin  _et al._ [2018] D. A. Bandurin, A. V. Shytov, L. S. Levitov, R. K. Kumar, A. I. Berdyugin, M. Ben Shalom, I. V. Grigorieva, A. K. Geim, and G. Falkovich, Fluidity onset in graphene, Nature Communications 9, 4533 (2018).
  * Keser  _et al._ [2021] A. C. Keser, D. Q. Wang, O. Klochan, D. Y. H. Ho, O. A. Tkachenko, V. A. Tkachenko, D. Culcer, S. Adam, I. Farrer, D. A. Ritchie, O. P. Sushkov, and A. R. Hamilton, Geometric control of universal hydrodynamic flow in a two-dimensional electron fluid, Phys. Rev. X 11, 031030 (2021).
  * Gusev  _et al._ [2018a] G. M. Gusev, A. D. Levin, E. V. Levinson, and A. K. Bakarov, Viscous transport and Hall viscosity in a two-dimensional electron system, Phys. Rev. B 98, 161303(R) (2018a), publisher: American Physical Society.
  * Ginzburg  _et al._ [2021] L. V. Ginzburg, C. Gold, M. P. Röösli, C. Reichl, M. Berl, W. Wegscheider, T. Ihn, and K. Ensslin, Superballistic electron flow through a point contact in a Ga[Al]As heterostructure, Physical Review Research 3, 023033 (2021), arXiv: 2012.03570.
  * Sulpizio  _et al._ [2019] J. A. Sulpizio, L. Ella, A. Rozen, J. Birkbeck, D. J. Perello, D. Dutta, M. Ben-Shalom, T. Taniguchi, K. Watanabe, T. Holder, R. Queiroz, A. Principi, A. Stern, T. Scaffidi, A. K. Geim, and S. Ilani, Visualizing Poiseuille flow of hydrodynamic electrons, Nature 576, 75 (2019), iSBN: 1476-4687.
  * Ku  _et al._ [2020] M. J. H. Ku, T. X. Zhou, Q. Li, Y. J. Shin, J. K. Shi, C. Burch, L. E. Anderson, A. T. Pierce, Y. Xie, A. Hamo, U. Vool, H. Zhang, F. Casola, T. Taniguchi, K. Watanabe, M. M. Fogler, P. Kim, A. Yacoby, and R. L. Walsworth, Imaging viscous flow of the Dirac fluid in graphene, Nature 583, 537 (2020), iSBN: 1476-4687.
  * Ella  _et al._ [2019] L. Ella, A. Rozen, J. Birkbeck, M. Ben-Shalom, D. Perello, J. Zultak, T. Taniguchi, K. Watanabe, A. K. Geim, S. Ilani, and J. A. Sulpizio, Simultaneous voltage and current density imaging of flowing electrons in two dimensions, Nature Nanotechnology 14, 480 (2019), number: 5 Publisher: Nature Publishing Group.
  * Govorov and Heremans [2004] A. O. Govorov and J. J. Heremans, Hydrodynamic Effects in Interacting Fermi Electron Jets, Phys. Rev. Lett. 92, 026803 (2004), publisher: American Physical Society.
  * Kaya [2013] I. I. Kaya, Nonequilibrium transport and the bernoulli effect of electrons in a two-dimensional electron gas, Modern Physics Letters B 27, 1330001 (2013), _eprint: https://doi.org/10.1142/S0217984913300019.
  * Braem  _et al._ [2018] B. A. Braem, F. M. D. Pellegrino, A. Principi, M. Röösli, C. Gold, S. Hennel, J. V. Koski, M. Berl, W. Dietsche, W. Wegscheider, M. Polini, T. Ihn, and K. Ensslin, Scanning gate microscopy in a viscous electron fluid, Physical Review B 98, 241304 (2018), publisher: American Physical Society.
  * Berdyugin  _et al._ [2019] A. I. Berdyugin, S. G. Xu, F. M. D. Pellegrino, R. Krishna Kumar, A. Principi, I. Torre, M. Ben Shalom, T. Taniguchi, K. Watanabe, I. V. Grigorieva, M. Polini, A. K. Geim, and D. A. Bandurin, Measuring Hall viscosity of graphene’s electron fluid, Science 364, 162 (2019), publisher: American Association for the Advancement of Science.
  * Gusev  _et al._ [2018b] G. M. Gusev, A. D. Levin, E. V. Levinson, and A. K. Bakarov, Viscous electron flow in mesoscopic two-dimensional electron gas, AIP Advances 8, 025318 (2018b).
  * Shi  _et al._ [2014] Q. Shi, P. D. Martin, Q. A. Ebner, M. A. Zudov, L. N. Pfeiffer, and K. W. West, Colossal negative magnetoresistance in a two-dimensional electron gas, Phys. Rev. B 89, 201301(R) (2014), publisher: American Physical Society.
  * Mani  _et al._ [2013] R. G. Mani, A. Kriisa, and W. Wegscheider, Size-dependent giant-magnetoresistance in millimeter scale GaAs/AlGaAs 2D electron devices, Scientific Reports 3, 2747 EP (2013), publisher: The Author(s) SN -.
  * Wang  _et al._ [2022] X. Wang, P. Jia, R.-R. Du, L. N. Pfeiffer, K. W. Baldwin, and K. W. West, Hydrodynamic charge transport in gaas/algaas ultrahigh-mobility two-dimensional electron gas (2022).
  * Crossno  _et al._ [2016] J. Crossno, J. K. Shi, K. Wang, X. Liu, A. Harzheim, A. Lucas, S. Sachdev, P. Kim, T. Taniguchi, K. Watanabe, T. A. Ohki, and K. C. Fong, Observation of the Dirac fluid and the breakdown of the Wiedemann-Franz law in graphene, Science 351, 1058 (2016).
  * Gooth  _et al._ [2018] J. Gooth, F. Menges, N. Kumar, V. Süss, C. Shekhar, Y. Sun, U. Drechsler, R. Zierold, C. Felser, and B. Gotsmann, Thermal and electrical signatures of a hydrodynamic electron fluid in tungsten diphosphide, Nature Communications 9, 4093 (2018).
  * Lucas and Das Sarma [2018] A. Lucas and S. Das Sarma, Electronic hydrodynamics and the breakdown of the wiedemann-franz and mott laws in interacting metals, Phys. Rev. B 97, 245128 (2018).
  * Jaoui  _et al._ [2021] A. Jaoui, B. Fauqué, and K. Behnia, Thermal resistivity and hydrodynamics of the degenerate electron fluid in antimony, Nature Communications 12, 195 (2021), number: 1 Publisher: Nature Publishing Group.
  * Ahn and Das Sarma [2022] S. Ahn and S. Das Sarma, Hydrodynamics, viscous electron fluid, and wiedeman-franz law in two-dimensional semiconductors, Phys. Rev. B 106, L081303 (2022).
  * Dai  _et al._ [2010] Y. Dai, R. R. Du, L. N. Pfeiffer, and K. W. West, Observation of a cyclotron harmonic spike in microwave-induced resistances in ultraclean $\mathrm{GaAs}/\mathrm{AlGaAs}$ quantum wells, Phys. Rev. Lett. 105, 246802 (2010).
  * Hatke  _et al._ [2011] A. T. Hatke, M. A. Zudov, L. N. Pfeiffer, and K. W. West, Giant microwave photoresistivity in high-mobility quantum hall systems, Phys. Rev. B 83, 121301 (2011).
  * Białek  _et al._ [2015] M. Białek, J. Łusakowski, M. Czapkiewicz, J. Wróbel, and V. Umansky, Photoresponse of a two-dimensional electron gas at the second harmonic of the cyclotron resonance, Phys. Rev. B 91, 045437 (2015).
  * Alekseev and Alekseeva [2019] P. S. Alekseev and A. P. Alekseeva, Transverse magnetosonic waves and viscoelastic resonance in a two-dimensional highly viscous electron fluid, Phys. Rev. Lett. 123, 236801 (2019).
  * Gallagher  _et al._ [2019] P. Gallagher, C.-S. Yang, T. Lyu, F. Tian, R. Kou, H. Zhang, K. Watanabe, T. Taniguchi, and F. Wang, Quantum-critical conductivity of the Dirac fluid in graphene, Science 364, 158 (2019), publisher: American Association for the Advancement of Science.
  * Stern  _et al._ [2021] A. Stern, T. Scaffidi, O. Reuven, C. Kumar, J. Birkbeck, and S. Ilani, Spread and erase – How electron hydrodynamics can eliminate the Landauer-Sharvin resistance, arXiv:2110.15369 [cond-mat] (2021), arXiv: 2110.15369.
  * Varnavides  _et al._ [2020] G. Varnavides, A. S. Jermyn, P. Anikeeva, C. Felser, and P. Narang, Electron hydrodynamics in anisotropic materials, Nature Communications 11, 4710 (2020), number: 1 Publisher: Nature Publishing Group.
  * Link  _et al._ [2018] J. M. Link, B. N. Narozhny, E. I. Kiselev, and J. Schmalian, Out-of-Bounds Hydrodynamics in Anisotropic Dirac Fluids, Phys. Rev. Lett. 120, 196801 (2018), publisher: American Physical Society.
  * Galitski  _et al._ [2018] V. Galitski, M. Kargarian, and S. Syzranov, Dynamo Effect and Turbulence in Hydrodynamic Weyl Metals, Phys. Rev. Lett. 121, 176603 (2018), publisher: American Physical Society.
  * Tatara [2021] G. Tatara, Hydrodynamic theory of vorticity-induced spin transport, Physical Review B 104, 184414 (2021), publisher: American Physical Society.
  * Doornenbal  _et al._ [2019] R. J. Doornenbal, M. Polini, and R. A. Duine, Spin–vorticity coupling in viscous electron fluids, Journal of Physics: Materials 2, 015006 (2019), publisher: IOP Publishing.
  * Matsuo  _et al._ [2020] M. Matsuo, D. A. Bandurin, Y. Ohnuma, Y. Tsutsumi, and S. Maekawa, Spin hydrodynamic generation in graphene, arXiv:2005.01493 [cond-mat] (2020), arXiv: 2005.01493 version: 1.
  * Takahashi  _et al._ [2016] R. Takahashi, M. Matsuo, M. Ono, K. Harii, H. Chudo, S. Okayasu, J. Ieda, S. Takahashi, S. Maekawa, and E. Saitoh, Spin hydrodynamic generation, Nature Physics 12, 52 (2016), number: 1 Publisher: Nature Publishing Group.
  * Takahashi  _et al._ [2020] R. Takahashi, H. Chudo, M. Matsuo, K. Harii, Y. Ohnuma, S. Maekawa, and E. Saitoh, Giant spin hydrodynamic generation in laminar flow, Nature Communications 11, 3009 (2020), number: 1 Publisher: Nature Publishing Group.
  * Landau and Lifshitz [2013] L. Landau and E. Lifshitz,  _Fluid Mechanics_, Vol. 6 (Elsevier Science, 2013).
  * Alekseev and Dmitriev [2020] P. S. Alekseev and A. P. Dmitriev, Viscosity of two-dimensional electrons, Physical Review B 102, 241409 (2020).
  * Moessner  _et al._ [2018] R. Moessner, P. Surówka, and P. Witkowski, Pulsating flow and boundary layers in viscous electronic hydrodynamics, Physical Review B 97, 161112 (2018), arXiv: 1710.00354.
  * Levchenko and Schmalian [2020] A. Levchenko and J. Schmalian, Transport properties of strongly coupled electron–phonon liquids, Annals of Physics 419, 168218 (2020).
  * Gusev  _et al._ [2020] G. M. Gusev, A. S. Jaroshevich, A. D. Levin, Z. D. Kvon, and A. K. Bakarov, Stokes flow around an obstacle in viscous two-dimensional electron liquid, Scientific Reports 10, 7860 (2020), iSBN: 2045-2322.
  * Lucas [2017] A. Lucas, Stokes paradox in electronic Fermi liquids, Phys. Rev. B 95, 115425 (2017), publisher: American Physical Society.
  * Moessner  _et al._ [2019] R. Moessner, N. Morales-Durán, P. Surówka, and P. Witkowski, Boundary condition and geometry engineering in electronic hydrodynamics, Physical Review B 100, 155115 (2019), arXiv: 1903.08037.
  * Danan  _et al._ [1968] H. Danan, A. Herr, and A. J. P. Meyer, New Determinations of the Saturation Magnetization of Nickel and Iron, Journal of Applied Physics 39, 669 (1968).
  * Tumanski [2011] S. Tumanski, Magnetic Materials, in  _Handbook of Magnetic Measurements_, Vol. 20110781 (CRC Press, 2011) pp. 117–158, series Title: Series in Sensors.


9: return $\theta_{t}$

######  Proposition 7.

$\mathsf{RobustAccel}$ correctly returns $\theta$ satisfying (26) with
probability $\geq 1-\delta$. It runs in
$O\left(\sqrt{\kappa}\log\left(\frac{R_{0}\sqrt{L}}{\sigma\sqrt{\epsilon}}\right)\right)$
calls to $\mathcal{O}_{\textup{ng}}$, and
$O\left(\sqrt{\kappa}d\log\left(\frac{R_{0}\sqrt{L}}{\sigma\sqrt{\epsilon}}\right)\right)$
additional time.

###### Proof.

Correctness is immediate by iterating the guarantees of Lemma 14 $T$ times,
and taking a union bound over all (at most $N$) calls to
$\mathcal{O}_{\textup{ng}}$, the only source of randomness in the algorithm.
The runtime follows from examining $\mathsf{HalfRadiusAccel}$ and
$\mathcal{O}_{\textup{ng}}$, since all operations take $O(d)$ time other than
calls to $\mathcal{O}_{\textup{ng}}$. ∎

By combining Proposition 7 with Corollary 1 and 2, we derive the following
conclusions.

######  Theorem 6.

Under Models 1, 4, supposing $\epsilon\kappa^{2}$ is sufficiently small, given
$\theta_{0}\in\mathbb{R}^{d}$ and
$\left\lVert\theta_{0}-\theta^{\star}\right\rVert_{\boldsymbol{\Sigma}^{\star}}\leq
R_{0}$, $\mathsf{RobustAccel}$ using the noisy gradient oracle of Corollary 1
returns $\theta$ with
$\left\lVert\theta-\theta^{\star}\right\rVert_{\boldsymbol{\Sigma}^{\star}}=O\left(\sigma\kappa\sqrt{\epsilon}\right)$
with probability at least $1-\delta$. The algorithm runs in

$O\left(nd\sqrt{\kappa}\log\left(\frac{R_{0}}{\sigma\sqrt{\epsilon}}\right)\log^{3}(n)\log^{2}\left(\frac{n\log\left(\frac{R_{0}}{\sigma}\right)}{\delta\epsilon}\right)\right)\text{
time,}$

where $n$ is the dataset size of Proposition 3. The sample complexity of the
method is

$O\left(\log\left(\frac{\log\left(\frac{R_{0}}{\sigma}\right)}{\delta\epsilon}\right)\cdot\left(\frac{d\log(d/\epsilon)}{\epsilon}\right)\right).$

######  Theorem 7.

Under Models 1, 2, and 5, supposing $\epsilon\kappa^{2}$ is sufficiently small
for $\kappa:=\max(1,\frac{L}{\mu})$, given $\theta_{0}\in\mathbb{R}^{d}$ and
$\left\lVert\theta_{0}-\theta^{\star}_{\textup{reg}}\right\rVert_{2}\leq
R_{0}$, $\mathsf{RobustAccel}$ using the noisy gradient oracle of Corollary 2
returns $\theta$ with
$\left\lVert\theta-\theta^{\star}_{\textup{reg}}\right\rVert_{2}=O\left(\sqrt{\frac{\kappa\epsilon}{\mu}}\right)$
with probability at least $1-\delta$. The algorithm runs in

$O\left(nd\sqrt{\kappa}\log\left(\frac{R_{0}\sqrt{L+\mu}}{\epsilon}\right)\log^{3}(n)\log^{2}\left(\frac{n\log\left(R_{0}\sqrt{L+\mu}\right)}{\delta\epsilon}\right)\right)\text{
time,}$

where $n$ is the dataset size of Proposition 4. The sample complexity of the
method is

$O\left(\log\left(\frac{\log\left(R_{0}\sqrt{L+\mu}\right)}{\delta\epsilon}\right)\cdot\left(\frac{d\log(d/\epsilon)}{\epsilon}\right)\right).$

We remark that Theorem 6 can afford to reuse the same samples to construct
gradient estimates for all $\theta$ we query per Assumption 2: though the set
$G_{\theta}$ may change per $\theta$, our noisy estimator also provides a
per-$\theta$ guarantee (and hence does not require the set to be consistent
across calls).

##  5 Lipschitz generalized linear models

In this section, we give an algorithm for minimizing the regularized Moreau
envelopes of Lipschitz statistical optimization problems under the strong
contamination model, following the exposition of Section 2.4. Concretely, we
recall we wish to compute an approximation to

$\begin{gathered}\theta^{\star}_{\textup{env}}:=\textup{argmin}_{\theta\in\mathbb{R}^{d}}\left\\{F^{\star}_{\lambda}\left(\theta\right)+\frac{\mu}{2}\left\lVert\theta\right\rVert_{2}^{2}\right\\},\text{
where
}F^{\star}(\theta)=\operatorname*{\mathbb{E}}_{f\sim\mathcal{D}_{f}}[f(\theta)],\\\
\text{and
}F^{\star}_{\lambda}(\theta):=\inf_{\theta^{\prime}}\left\\{F^{\star}(\theta^{\prime})+\frac{1}{2\lambda}\left\lVert\theta-\theta^{\prime}\right\rVert_{2}^{2}\right\\}.\end{gathered}$
(27)

Recall that in Corollary 2, we developed a noisy gradient oracle for
$F^{\star}$, as long as our function distribution is captured by Model 6.
However, techniques of Section 4 do not immediately apply to this setting, as
$F^{\star}$ is not smooth. On the other hand, we do not have direct access to
$F^{\star}_{\lambda}$.

We ameliorate this by developing a noisy gradient oracle (Definition 4) for
the Moreau envelope $F^{\star}_{\lambda}$ in Section 5.1, under only
Assumption 3; this will allow us to apply the acceleration techniques of
Section 4 to the problem (27), which we complete in Section 5.2.
Interestingly, our noisy gradient oracle for $F^{\star}_{\lambda}$ will have
noise and runtime guarantees _independent_ of the envelope parameter
$\lambda$, allowing for a range of statistical and runtime tradeoffs for
applications.

###  5.1 Noisy gradient oracle for the Moreau envelope

In this section, we give an efficient reduction which enables the construction
of a noisy gradient oracle for $F^{\star}_{\lambda}$, assuming a radiusless
noisy gradient oracle for $F^{\star}$, and that $F^{\star}$ is Lipschitz. We
note that both of these assumptions hold under Model 6: we showed in Lemma 4
that $F^{\star}$ is $\sqrt{L}$-Lipschitz, and constructed a radiusless noisy
gradient oracle in Corollary 2.

To begin, we recall standard facts about the Moreau envelope
$F^{\star}_{\lambda}$, which can be found in e.g. [PB14].

######  Fact 2.

$F^{\star}_{\lambda}$ is $\lambda^{-1}$-smooth, satisfies $0\leq
F^{\star}(\theta)-F^{\star}_{\lambda}(\theta)\leq L\lambda$ for all
$\theta\in\mathbb{R}^{d}$, and has gradient

$\nabla
F^{\star}_{\lambda}(\theta)=\frac{1}{\lambda}\left(\theta-\textup{prox}_{\lambda,F^{\star}}(\theta)\right),\text{
where
}\textup{prox}_{\lambda,F^{\star}}(\theta):=\textup{argmin}_{\theta^{\prime}}\left\\{F^{\star}(\theta^{\prime})+\frac{1}{2\lambda}\left\lVert\theta-\theta^{\prime}\right\rVert_{2}^{2}\right\\}.$

Fact 2 demonstrates that to construct a noisy gradient oracle for
$F^{\star}_{\lambda}$, it suffices to approximate the minimizer of the
subproblem defining the $\textup{prox}_{\lambda,F^{\star}}$ operator. To this
end, we give a simple algorithm which approximates this proximal minimizer,
based on noisy projected gradient descent.

Algorithm 6
$\mathsf{ApproxMoreauMinimizer}(\bar{\theta},\mathcal{O}_{\textup{ng}},\delta)$

1: Input: $\mathcal{O}_{\textup{ng}}$, a $(L,1,\frac{\delta}{T})$-radiusless
noisy gradient oracle for $\sqrt{L}$-Lipschitz
$F^{\star}:\mathbb{R}^{d}\to\mathbb{R}$ for
$T=O\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)$,
$\bar{\theta}\in\mathbb{R}^{d}$, $\delta\in(0,1)$

2: Output: With probability $\geq 1-\delta$, $\hat{\theta}$ satisfying for a
universal constant $C_{\text{env}}$,
$\left\lVert\hat{\theta}-\textup{prox}_{\lambda,F^{\star}}(\bar{\theta})\right\rVert_{2}\leq
C_{\text{env}}\sqrt{L\epsilon}\lambda.$ (28)

3: $T\leftarrow O\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)$ for a
sufficiently large constant, $t\leftarrow 0$,
$\theta_{0}\leftarrow\bar{\theta}$,
$\eta\leftarrow\frac{4C_{\textup{ng}}^{2}\epsilon\lambda}{5}$

4: while $t<T$ do

5:
$g_{t}\leftarrow\mathcal{O}_{\textup{ng}}(\theta_{t},\infty,\frac{\delta}{T})+\frac{1}{\gamma}(\theta_{t}-\bar{\theta})$

6: $\theta_{t+1}\leftarrow\text{Proj}_{\mathbb{B}}(\theta_{t}-\eta g_{t})$,
where Proj is the $\ell_{2}$ projection and
$\mathbb{B}:=\left\\{\theta\mid\left\lVert\theta-\bar{\theta}\right\rVert_{2}\leq
2\sqrt{L}\lambda\right\\}$

7: $t\leftarrow t+1$

8: end while

9: return $\theta_{t}$

We now begin our analysis of $\mathsf{ApproxMoreauMinimizer}$. In the
following discussion, for notational simplicity define
$\theta^{\star}_{\bar{\theta}}:=\textup{prox}_{\lambda,F^{\star}}(\bar{\theta})$
to be the exact minimizer of the proximal subproblem. We require a simple
helper bound showing $\theta^{\star}_{\bar{\theta}}$ does not lie too far from
$\bar{\theta}$.

######  Lemma 15.

For
$\mathbb{B}:=\left\\{\theta\mid\left\lVert\theta-\bar{\theta}\right\rVert_{2}\leq
2\sqrt{L}\lambda\right\\}$ and
$\theta^{\star}_{\bar{\theta}}:=\textup{prox}_{\lambda,F^{\star}}(\bar{\theta})$,
$\theta^{\star}_{\bar{\theta}}\in\mathbb{B}$.

###### Proof.

Let
$R:=\left\lVert\theta^{\star}_{\bar{\theta}}-\bar{\theta}\right\rVert_{2}$.
Since $\theta^{\star}_{\bar{\theta}}$ minimizes the proximal subproblem and
$F^{\star}$ is convex,

$\displaystyle
F^{\star}\left(\theta^{\star}_{\bar{\theta}}\right)+\frac{R^{2}}{2\lambda}\leq
F^{\star}\left(\bar{\theta}\right)\leq
F^{\star}\left(\theta^{\star}_{\bar{\theta}}\right)+\left\langle\nabla
F^{\star}\left(\bar{\theta}\right),\theta^{\star}_{\bar{\theta}}-\bar{\theta}\right\rangle\implies\frac{R^{2}}{2\lambda}\leq\sqrt{L}R.$

∎

We now prove correctness of $\mathsf{ApproxMoreauMinimizer}$.

######  Lemma 16.

$\mathsf{ApproxMoreauMinimizer}$ correctly computes $\hat{\theta}$ satisfying
(28) in $O\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)$ calls to
$\mathcal{O}_{\textup{ng}}$, with probability $\geq 1-\delta$.

###### Proof.

We assume throughout correctness of all calls to $\mathcal{O}_{\textup{ng}}$,
which follows from a union bound. Consider some iteration $0\leq t<T$, and let
$\hat{\theta}_{t+1}:=\theta_{t}-\eta g_{t}$ be the unprojected iterate. Since
Euclidean projections decrease distances to points within a set (see e.g.
Lemma 3.1, [Bub15]), letting $g_{t}=e_{t}+\nabla
F^{\star}(\theta_{t})+\frac{1}{\lambda}(\theta_{t}-\bar{\theta})$, where
$\left\lVert e_{t}\right\rVert_{2}\leq C_{\textup{ng}}\sqrt{L\epsilon}$,

$\displaystyle\frac{1}{2}\left\lVert\theta_{t+1}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{1}{2}\left\lVert\hat{\theta}_{t+1}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}=\frac{1}{2}\left\lVert\theta_{t}-\eta
g_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}$ (29)
$\displaystyle=\frac{1}{2}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}-\eta\left\langle
e_{t}+\nabla
F^{\star}(\theta_{t})+\frac{1}{\lambda}(\theta_{t}-\bar{\theta}),\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rangle+\frac{\eta^{2}}{2}\left\lVert
g_{t}\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{1}{2}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}-\frac{\eta}{\lambda}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}+\eta\left\lVert
e_{t}\right\rVert_{2}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}+\frac{\eta^{2}}{2}\left\lVert
g_{t}\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{1}{2}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}-\frac{\eta}{\lambda}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}+\eta
C_{\textup{ng}}\sqrt{L\epsilon}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}+5\eta^{2}L.$

In the third line, we lower bounded $\left\langle\nabla
F^{\star}(\theta_{t})+\frac{1}{\lambda}(\theta_{t}-\bar{\theta}),\bar{\theta}-\theta^{\star}_{\bar{\theta}}\right\rangle$
by using strong convexity of
$F^{\star}+\frac{1}{\lambda}\left\lVert\cdot-\bar{\theta}\right\rVert_{2}^{2}$;
in the last line, we used the assumed bound on $e_{t}$ as well as

$\left\lVert g_{t}\right\rVert_{2}\leq\left\lVert\nabla
F^{\star}(\theta_{t})\right\rVert_{2}+\left\lVert
e_{t}\right\rVert_{2}+\frac{1}{\lambda}\left\lVert\theta_{t}-\bar{\theta}\right\rVert_{2}\leq
3\sqrt{L}+C_{\textup{ng}}\sqrt{L\epsilon}\leq\sqrt{10L},$

for sufficiently small $\epsilon$. Next, consider some iteration $t$ where
iterate $\theta_{t}$ satisfies

$\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}\geq
4C_{\textup{ng}}\sqrt{L\epsilon}\lambda.$ (30)

On this iteration, we have from the definition of $\eta$ that

$\displaystyle\eta
C_{\textup{ng}}\sqrt{L\epsilon}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}\leq\frac{\eta}{4\lambda}\left\lVert\theta-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2},\;5\eta^{2}L\leq\frac{\eta}{4\lambda}\left\lVert\theta-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}.$

Plugging these bounds back into (29), on any iteration where (30) holds,

$\displaystyle\left\lVert\theta_{t+1}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}\leq\left(1-\frac{\eta}{\lambda}\right)\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}=\left(1-\frac{4}{5}C_{\textup{ng}}^{2}\epsilon\right)\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}.$

Because the squared distance
$\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}^{2}$ is
bounded by $16L\lambda^{2}$ initially and decreases by a factor of
$O(\epsilon)$ every iteration until (30) no longer holds, it will reach an
iteration where (30) no longer holds within $T$ iterations. Finally, by (29),
in every iteration $t$ after the first where (30) is violated, either the
squared distance to $\theta^{\star}_{\bar{\theta}}$ goes down, or it can go up
by at most

$\displaystyle\eta
C_{\textup{ng}}\sqrt{L\epsilon}\left\lVert\theta_{t}-\theta^{\star}_{\bar{\theta}}\right\rVert_{2}+5\eta^{2}L=O\left(\epsilon^{2}\lambda^{2}L\right).$

Here we used our earlier claim that the distance can only go up when (30) is
false. Thus, the squared distance will never be more than
$16C_{\textup{ng}}^{2}L(\epsilon+O(\epsilon^{2}))\lambda^{2}$ within $T$
iterations, as desired. ∎

By using the gradient characterization in Fact 2 and the noisy gradient oracle
implementation of Corollary 2, we conclude this section with our Moreau
envelope noisy gradient oracle claim.

######  Corollary 3.

Consider a robust Lipschitz stochastic optimization instance where we have
sample access to datasets
$\mathbf{X}=\\{X_{i}\\}_{i\in[n]}\in\mathbb{R}^{n\times d}$ and
$y=\\{y_{i}\\}_{i\in[n]}\in\mathbb{R}^{n}$ under Models 1, 2, 6 with sample
size $n$ corresponding to Proposition 4. For

$F(\theta)=F^{\star}_{\lambda}(\theta)+\frac{\mu}{2}\left\lVert\theta\right\rVert_{2}^{2},$

we can construct a $(L,O(1),\delta)$-radiusless noisy gradient oracle in
$O(\frac{nd}{\epsilon}\log^{3}(n)\log^{2}(\frac{n}{\delta\epsilon})\log(\frac{1}{\epsilon}))$
time. The sample complexity of our noisy gradient oracle is

$O\left(\log\left(\frac{1}{\delta\epsilon}\right)\cdot\left(\frac{d\log(d/\epsilon)}{\epsilon}\right)\right).$

###  5.2 Accelerated optimization of the regularized Moreau envelope

We conclude by combining Proposition 7, the smoothness bound from Fact 2, and
the noisy gradient oracle implementation of Corollary 3 to give this section’s
main result, Theorem 8.

######  Theorem 8.

Under Models 1, 2, and 6, supposing $\epsilon\kappa^{2}$ is sufficiently small
for $\kappa:=\max(1,\frac{1}{\lambda\mu})$, given
$\theta_{0}\in\mathbb{R}^{d}$ and
$\left\lVert\theta_{0}-\theta^{\star}_{\textup{env}}\right\rVert_{2}\leq
R_{0}$, $\mathsf{RobustAccel}$ using the noisy gradient oracle of Corollary 3
returns $\theta$ with
$\left\lVert\theta-\theta^{\star}_{\textup{env}}\right\rVert_{2}=O\left(\sqrt{\frac{\kappa\epsilon}{\mu}}\right)$
with probability at least $1-\delta$. The algorithm runs in

$O\left(\frac{nd\sqrt{\kappa}}{\epsilon}\log\left(\frac{R_{0}\sqrt{\lambda^{-1}+\mu}}{\epsilon}\right)\log^{3}(n)\log^{2}\left(\frac{n\log\left(R_{0}\sqrt{\lambda^{-1}+\mu}\right)}{\delta\epsilon}\right)\log\left(\frac{1}{\epsilon}\right)\right)\text{
time,}$

where $n$ is the dataset size of Proposition 4. The sample complexity of the
method is

$O\left(\log\left(\frac{\log\left(R_{0}\sqrt{\lambda^{-1}+\mu}\right)}{\delta\epsilon}\right)\cdot\left(\frac{d\log(d/\epsilon)}{\epsilon}\right)\right).$

Combined with Fact 2, Theorem 8 offers a range of tradeoffs by tuning the
parameter $\lambda$: the smaller $\lambda$ is, the more the Moreau envelope
resembles the original function, but the statistical and runtime guarantees
offered by Theorem 8 become correspondingly weaker.

### Acknowledgments

KT is supported by NSF Grant CCF-1955039 and the Alfred P. Sloan Foundation.

## References

  * [Ach03] Dimitris Achlioptas.  Database-friendly random projections: Johnson-lindenstrauss with binary coins.  J. Comput. Syst. Sci., 66(4):671–687, 2003.
  * [Ans60] Frank J Anscombe.  Rejection of outliers.  Technometrics, 2(2):123–146, 1960.
  * [AO17] Zeyuan Allen-Zhu and Lorenzo Orecchia.  Linear coupling: An ultimate unification of gradient and mirror descent.  In Proceedings of the 8th Innovations in Theoretical Computer Science, ITCS ’17, 2017.
  * [BBH+12] Boaz Barak, Fernando GSL Brandao, Aram W Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou.  Hypercontractivity, sum-of-squares proofs, and their applications.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 307–326, 2012.
  * [BDLS17] Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh.  Computationally efficient robust sparse estimation in high dimensions.  In Conference on Learning Theory, pages 169–212, 2017.
  * [BGG+19] Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani.  Approximability of $p\to q$ matrix norms: generalized Krivine rounding and hypercontractive hardness.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1358–1368. SIAM, 2019.
  * [BJL+19] Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford.  Complexity of highly parallel non-smooth convex optimization.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13900–13909, 2019.
  * [BP21] Ainesh Bakshi and Adarsh Prasad.  Robust linear regression: Optimal rates in polynomial time.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, 2021.
  * [Bub15] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  Found. Trends Mach. Learn., 8(3-4):231–357, 2015.
  * [CAT+20] Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni, Michael I. Jordan, Nicolas Flammarion, and Peter L. Bartlett.  Optimal robust linear regression in nearly linear time.  CoRR, abs/2007.08137, 2020.
  * [CDG19] Yu Cheng, Ilias Diakonikolas, and Rong Ge.  High-dimensional robust mean estimation in nearly-linear time.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2755–2771, 2019.
  * [CDO18] Michael Cohen, Jelena Diakonikolas, and Lorenzo Orecchia.  On acceleration with noise-corrupted gradients.  In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 1018–1027, 2018.
  * [CJJ+20] Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian.  Acceleration with a ball optimization oracle.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [CJJS21] Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford.  Thinking inside the ball: Near-optimal minimization of the maximal loss.  CoRR, abs/2105.01778, 2021.
  * [CSV17a] Moses Charikar, Jacob Steinhardt, and Gregory Valiant.  Learning from untrusted data.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47–60, 2017.
  * [CSV17b] Moses Charikar, Jacob Steinhardt, and Gregory Valiant.  Learning from untrusted data.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 47–60, 2017.
  * [d’A08] Alexandre d’Aspremont.  Smooth optimization with approximate gradient.  SIAM J. Optim., 19(3):1171–1183, 2008.
  * [DG16] Pavel E. Dvurechensky and Alexander V. Gasnikov.  Stochastic intermediate gradient method for convex problems with stochastic inexact oracle.  J. Optim. Theory Appl., 171(1):121–145, 2016.
  * [DGN14] Olivier Devolder, François Glineur, and Yurii E. Nesterov.  First-order methods of smooth convex optimization with inexact oracle.  Math. Program., 146(1-2):37–75, 2014.
  * [DHL19] Yihe Dong, Samuel B. Hopkins, and Jerry Li.  Quantum entropy scoring for fast robust mean estimation and improved outlier detection.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 6065–6075, 2019.
  * [DK19] Ilias Diakonikolas and Daniel M Kane.  Recent advances in algorithmic high-dimensional robust statistics.  arXiv preprint arXiv:1911.05911, 2019.
  * [DKK+16] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robust estimators in high dimensions without the computational intractability.  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 655–664, 2016.
  * [DKK+17] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Being robust (in high dimensions) can be practical.  In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 999–1008, 2017.
  * [DKK+19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart.  Sever: A robust meta-algorithm for stochastic optimization.  In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 1596–1606, 2019.
  * [DKK+21] Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian.  Clustering mixture models in almost-linear time via list-decodable mean estimation.  Preprint, 2021.
  * [DKS19] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart.  Efficient algorithms and lower bounds for robust linear regression.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2745–2754, 2019.
  * [Gor10] Rachel A. Gordon.  Regression Analysis for the Social Sciences.  Routledge, 2010.
  * [Hub64] Peter J Huber.  Robust estimation of a location parameter.  The Annals of Mathematical Statistics, 35(1):73–101, 1964.
  * [Hub04] Peter J Huber.  Robust statistics, volume 523.  John Wiley & Sons, 2004.
  * [JLT20] Arun Jambulapati, Jerry Li, and Kevin Tian.  Robust sub-gaussian principal component analysis and width-independent schatten packing.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [KKK19] Sushrut Karmalkar, Adam R. Klivans, and Pravesh Kothari.  List-decodable linear regression.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 7423–7432, 2019.
  * [KKM18] Adam R. Klivans, Pravesh K. Kothari, and Raghu Meka.  Efficient algorithms for outlier-robust regression.  In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, pages 1420–1430, 2018.
  * [Li18] Jerry Zheng Li.  Principled approaches to robust machine learning and beyond.  PhD thesis, Massachusetts Institute of Technology, Cambridge, USA, 2018\.
  * [LRV16] Kevin A. Lai, Anup B. Rao, and Santosh S. Vempala.  Agnostic estimation of mean and covariance.  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 665–674, 2016.
  * [MM15] Cameron Musco and Christopher Musco.  Randomized block krylov methods for stronger and faster approximate singular value decomposition.  In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1396–1404, 2015.
  * [MRJ19] Hesameddin Mohammadi, Meisam Razaviyayn, and Mihailo R. Jovanovic.  Performance of noisy nesterov’s accelerated method for strongly convex optimization problems.  In 2019 American Control Conference, ACC 2019, Philadelphia, PA, USA, July 10-12, 2019, pages 3426–3431, 2019.
  * [MS13] Renato D. C. Monteiro and Benar Fux Svaiter.  An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.  SIAM J. Optim., 23(2):1092–1125, 2013.
  * [Nes83] Yurii Nesterov.  A method for solving a convex programming problem with convergence rate $o(1/k^{2})$.  Doklady AN SSSR, 269:543–547, 1983.
  * [Nes03] Yurii Nesterov.  Introductory Lectures on Convex Optimization: A Basic Course, volume I.  2003\.
  * [PB14] Neal Parikh and Stephen P. Boyd.  Proximal algorithms.  Found. Trends Optim., 1(3):127–239, 2014.
  * [PSBR20] Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar.  Robust estimation via robust gradient estimation.  Journal of the Royal Statistical Society, Series B (Methodological), 82(3):601–627, 2020.
  * [RH17] Philippe Rigollet and Jan-Christian Hütter.  High-Dimensional Statistics.  2017\.
  * [Sho97] Ralph E. Showalter.  Monotone operators in banach space and nonlinear partial differential equations.  Mathematical Surveys and Monographs, 49:162–163, 1997.
  * [Smi12] Gary Smith.  Essential Statistics, Regression, and Econometrics.  Academic Press, 2012.
  * [Ste18] Jacob Steinhardt.  Robust learning: information theory and algorithms.  PhD thesis, Stanford University, Stanford, USA, 2018.
  * [TJNO20] Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh.  Projection efficient subgradient method and optimal nonsmooth frank-wolfe method.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [Tuk60] John W Tukey.  A survey of sampling from contaminated distributions.  Contributions to probability and statistics, pages 448–485, 1960\.
  * [Tuk75] John W. Tukey.  Mathematics and the picturing of data.  In Proceedings of the International Congress of Mathematicians, Vancouver, 1975, volume 2, pages 523–531, 1975.
  * [VGSM05] Eric Vittinghoff, David V. Glidden, Stephen C. Shiboski, and Charles E. McCulloch.  Regression Methods in Biostatistics: Linear, Logistic, Survival, and Repeated Measures Models.  Springer, 2005.
  * [ZH16] Zeyuan Allen Zhu and Elad Hazan.  Optimal black-box reductions between optimization objectives.  In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 1606–1614, 2016.
  * [Zhu17] Zeyuan Allen Zhu.  Katyusha: the first direct acceleration of stochastic gradient methods.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1200–1205, 2017.
  * [ZJS20] Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt.  Robust estimation via generalized quasi-gradients.  CoRR, abs/2005.14073, 2020.

##  Appendix A Deferred proofs from Section 2

###  A.1 Proof of Proposition 2

In this section, we prove Proposition 2, restated here for convenience.

See 2 Before we prove this lemma, we need the following useful technical
lemmata. The first shows that given a large enough sample of points from a
distribution with bounded second moment, there is a large subset of points
with bounded second moment.

######  Lemma 17 (Lemma A.20 in [DKK+17]).

Let $X_{1},\ldots,X_{n}$ be independent samples from a distribution
$\mathcal{D}$ with second moment matrix $\boldsymbol{\Sigma}^{\star}$, and let
$\epsilon>0$ be sufficiently small. There exists a universal constant $c>0$ so
that if $n\geq c\tfrac{d\log d}{\epsilon}$, we have that with probability
$0.99$, there exists a subset $S$ of size $(1-\epsilon)n$ satisfying

$\frac{1}{|S|}\sum_{i\in
S}X_{i}X_{i}^{\top}\preceq\frac{3}{2}\boldsymbol{\Sigma}^{\star}\;.$

We note that Lemma A.20 is stated for covariance as opposed to second moment,
but the same proof immediately implies the same result for second moment.

We also require the following bound.

######  Lemma 18 (Lemma 5.1 in [CAT+20]).

Let $X_{1},\ldots,X_{n}$ be independent samples from a distribution
$\mathcal{D}$ with second moment $\boldsymbol{\Sigma}^{\star}$, and let
$\epsilon>0$ be sufficiently small. Assume $\mathcal{D}$ is $2$-to-$4$
hypercontractive with parameter $C=O(1)$. There exists a universal constant
$c>0$ so that if $n\geq\tfrac{cd\log(d/\epsilon)}{\epsilon}$, then with
probability $1-\frac{1}{d^{2}}$, we have that for any $S\subset[n]$ of size
$(1-\epsilon)n$,

$\frac{1}{|S|}\sum_{i\in
S}X_{i}X_{i}^{\top}\succeq(1-\sqrt{\epsilon})\boldsymbol{\Sigma}^{\star}\;.$

Finally, we show our main helper lemma, which is used to prove Assumption 1.2
holds.

######  Lemma 19.

Let $\epsilon>0$ be sufficiently small. Let $X_{1},\ldots,X_{n}$ be $n$
samples from a $2$-to-$4$ hypercontractive distribution $\mathcal{D}$ with
parameter $C$ and second moment $\boldsymbol{\Sigma}^{\star}$. Then, there
exist universal constants $c,C_{\textup{est}}>0$ so that if

$n\geq c\left(\frac{d\log
d}{\epsilon^{4}}+\frac{d^{2}\log(d/\epsilon)}{\epsilon^{3}}\right),$

then with probability $0.99$, for every $u\in\mathbb{R}^{d}$, there exists an
$G\subseteq[n]$ satisfying $|G|\geq(1-\epsilon^{2})n$, and

$\left\lVert\frac{1}{|G|}\sum_{i\in G}\left\langle
X_{i},u\right\rangle^{2}X_{i}X_{i}^{\top}\right\rVert_{\textup{op}}\leq
C_{\textup{est}}L\left\lVert
u\right\rVert^{2}_{\boldsymbol{\Sigma}^{\star}}\;.$

###### Proof.

Without loss of generality (by scale invariance), it suffices to prove this
for all $u$ with $\left\lVert u\right\rVert_{\boldsymbol{\Sigma}^{\star}}=1$.
First, by Markov’s inequality with
$\operatorname*{\mathbb{E}}_{X\sim\mathcal{D}}[\left\lVert
X\right\rVert_{2}^{2}]=\textup{Tr}[\boldsymbol{\Sigma}^{\star}]\leq Ld$, we
have that

$\Pr_{X\sim\mathcal{D}}\left[\left\lVert
X\right\rVert_{2}^{2}\geq\frac{20Ld}{\epsilon^{2}}\right]\leq\frac{\epsilon^{2}}{20}\;.$

Hence, by Bernstein’s inequality, we have that with probability $0.999$,

$\frac{|\\{i:\left\lVert X_{i}\right\rVert_{2}^{2}\geq
20Ld\epsilon^{-2}\\}|}{n}\leq\frac{\epsilon^{2}}{10}\;.$ (31)

Condition on this event holding for the rest of the proof.

For any vector $u\in\mathbb{R}^{d}$ with $\left\lVert
u\right\rVert_{\boldsymbol{\Sigma}^{\star}}=1$, let
$H_{u}\subset\mathbb{R}^{d}$ be the set given by

$H_{u}=\left\\{x\in\mathbb{R}^{d}:\left\langle
x,u\right\rangle^{2}\geq\frac{10C_{2\to 4}^{1/2}}{\epsilon}\right\\}\;.$

Note that by Chebyshev’s inequality, since
$\operatorname*{\mathbb{E}}_{X\sim\mathcal{D}}[\left\langle
x,u\right\rangle^{4}]\leq C_{2\to 4}\left\lVert
u\right\rVert_{\boldsymbol{\Sigma}^{\star}}^{4}\leq C_{2\to 4}$, $\Pr_{X\sim
D}[X\in H_{u}]\leq\frac{\epsilon^{2}}{100}$. Furthermore, the collection of
sets $\\{H_{u}\\}_{\left\lVert u\right\rVert_{\boldsymbol{\Sigma}^{\star}}=1}$
has VC dimension $O(d)$, as each $H_{u}$ can be expressed as a restricted
intersection of parallel halfspaces, and it is well-known that VC dimension is
additive under intersection. Therefore, by the VC inequality, we know that if
$n\geq c\frac{d\log d}{\epsilon^{4}}$ for sufficiently large constant $c$,
with probability $0.999$, we have that

$\sup_{H_{u}}\frac{|\\{i:X_{i}\in H_{u}\\}|}{n}\leq\frac{\epsilon^{2}}{50}\;.$
(32)

Condition on this event holding for the rest of the proof. All expectations
throughout the remainder of the proof are taken with respect to
$X\sim\mathcal{D}$ for notational simplicity.

For any fixed $u$, we define the truncated fourth moment (contracted in the
direction $u$) by

$\mathbf{A}_{i}=\mathbf{A}_{i}(u)=\left\langle
X_{i},u\right\rangle^{2}X_{i}X_{i}^{\top}\mathbbm{1}\left[\left\langle
X_{i},u\right\rangle^{2}\leq\frac{20C_{2\to
4}^{1/2}}{\epsilon}~{}\mbox{and}~{}\left\lVert
X_{i}\right\rVert_{2}^{2}\leq\frac{20Ld}{\epsilon^{2}}\right].$

Note that

$\left\lVert\operatorname*{\mathbb{E}}\left[\mathbf{A}_{i}\right]\right\rVert_{\textup{op}}\leq\left\lVert\operatorname*{\mathbb{E}}\left[\left\langle
X_{i},u\right\rangle^{2}X_{i}X_{i}^{\top}\right]\right\rVert_{\textup{op}}=\sup_{\left\lVert
v\right\rVert_{2}=1}\operatorname*{\mathbb{E}}\left[\left\langle
X_{i},u\right\rangle^{2}\left\langle X_{i},v\right\rangle^{2}\right]\leq
C_{2\to 4}L\left\lVert u\right\rVert_{\boldsymbol{\Sigma}^{\star}}^{2}\;,$

by Cauchy-Schwarz and hypercontractivity. Moreover, by construction, the
spectral norm of $\mathbf{A}_{i}$ is bounded almost surely by
$\tfrac{400LC_{2\to 4}^{1/2}d}{\epsilon^{3}}.$ Hence, by a matrix Chernoff
bound, we get that if $n\geq c\tfrac{d^{2}\log(d/\epsilon)}{\epsilon^{3}}$ for
a sufficiently large constant $c$, then with probability $0.999$, we have that

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}\mathbf{A}_{i}(u)\right\rVert_{\textup{op}}\leq
2C_{2\to 4}L\left\lVert u\right\rVert_{\boldsymbol{\Sigma}^{\star}}^{2}\;.$
(33)

for all $u$ in a $\text{poly}(\frac{\epsilon}{d})$-net of the unit sphere in
the $\boldsymbol{\Sigma}^{\star}$ norm (which has cardinality
$(\frac{d}{\epsilon})^{O(d)}$ by Theorem 1.13 of [RH17]). Because we are union
bounding over $\text{poly}(d,\epsilon^{-1})$ samples, we have with high
probability that all $\left\lVert
X_{i}\right\rVert_{(\boldsymbol{\Sigma}^{\star})^{-1}}=\text{poly}(d,\epsilon^{-1})$.
Hence, it is straightforward to show that the bound (33) over our net implies
for all $\left\lVert u\right\rVert_{\boldsymbol{\Sigma}^{\star}}=1$,

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}\left\langle
X_{i},u\right\rangle^{2}X_{i}X_{i}^{\top}\mathbbm{1}\left[X_{i}\not\in
H_{u}~{}\mbox{and}~{}\left\lVert X_{i}\right\rVert_{2}^{2}\leq\frac{10C_{2\to
4}^{1/2}Ld}{\epsilon}\right]\right\rVert_{\textup{op}}\leq 2C_{2\to 4}L\;,$
(34)

Combining (31), (32), and (34) implies that for every $u$, the set
$G=\\{i:X_{i}\in H_{u}~{}\mbox{and}~{}\left\lVert
X_{i}\right\rVert_{2}^{2}\leq\frac{20Ld}{\epsilon^{2}}\\}$ satisfies the
conditions of the lemma. ∎

We are now ready to prove Proposition 2.

###### Proof of Proposition 2.

Condition 3 of Assumption 1 follows directly from Markov’s inequality, since
it is asking about the empirical average over $G$ of
$\delta^{2}\sim\mathcal{D}_{\delta}$; the adversary removing points can only
affect this upper bound by a constant factor (due to renormalization).

Next, let $[n]=G\cup B$ be the canonical decomposition of the corrupted set of
samples. By two applications of Lemma 17, with probability at least $0.99$,
there exists a set $G^{\prime}\subset G$ of size
$|G^{\prime}|\geq(1-\epsilon)|G|\geq(1-2\epsilon)n$ so that

$\displaystyle\frac{1}{|G^{\prime}|}\sum_{i\in G^{\prime}}X_{i}X_{i}^{\top}$
$\displaystyle\preceq\frac{3}{2}\boldsymbol{\Sigma}^{\star}\;,$ (35)
$\displaystyle\frac{1}{|G^{\prime}|}\sum_{i\in
G^{\prime}}\delta_{i}^{2}X_{i}X_{i}^{\top}$
$\displaystyle\preceq\frac{3}{2}\sigma^{2}\boldsymbol{\Sigma}^{\star}\;.$ (36)

Condition on the event that such a $G^{\prime}$ exists for the remainder of
the proof, and also condition on the event that Lemma 19 is satisfied. By a
union bound, these events happen together with probability at least $0.9$. We
will show that this $G^{\prime}$ will satisfy the conditions of the lemma. The
upper bound in Condition 1 of Assumption 1 is immediate, and similarly, the
lower bound follows from Lemma 18 and a standard convexity argument (since the
vertices of the polytope defining saturated weights are subsets of cardinality
$(1-O(\epsilon))|G|$).

It thus remains to prove Condition 2 of Assumption 1. To do so, we will first
prove (8) is satisfied with high probability. By Lemma 19 (adjusting by a
factor of $\alpha$ in the definition of $\epsilon^{2}$), there exists a set
$G^{\prime\prime}\subseteq G^{\prime}$ so that
$|G^{\prime\prime}|\geq(1-\frac{\epsilon^{2}}{\alpha})|G^{\prime}|$ so that

$\left\lVert\frac{1}{|G^{\prime\prime}|}\sum_{i\in
G^{\prime\prime}}\left\langle
X_{i},\theta-\theta^{\star}\right\rangle^{2}X_{i}X_{i}^{\top}\right\rVert_{\textup{op}}\leq
C_{\textup{est}}L\left\lVert\theta-\theta^{\star}\right\rVert^{2}_{\boldsymbol{\Sigma}^{\star}}\;.$

Hence, for this choice of $G^{\prime\prime}$, we have

$\displaystyle\textup{Cov}_{\tilde{w}}\left(\left\\{g_{i}(\theta)\right\\}_{i\in
G^{\prime\prime}}\right)$ $\displaystyle=\sum_{i\in
G^{\prime\prime}}\tilde{w}_{i}\left(\left\langle
X_{i},\theta-\theta^{\star}\right\rangle+\delta_{i}\right)^{2}X_{i}X_{i}^{\top}$
$\displaystyle\preceq 2\sum_{i\in G^{\prime\prime}}\tilde{w}_{i}\left\langle
X_{i},\theta-\theta^{\star}\right\rangle^{2}X_{i}X_{i}^{\top}+2\sum_{i\in
G}\tilde{w}_{i}\delta_{i}^{2}X_{i}X_{i}^{\top}$
$\displaystyle\preceq\frac{2(1+2\epsilon)}{|G^{\prime\prime}|}\sum_{i\in
G^{\prime\prime}}\left\langle
X_{i},\theta-\theta^{\star}\right\rangle^{2}X_{i}X_{i}^{\top}+\frac{2(1+2\epsilon)}{|G^{\prime}|}\sum_{i\in
G^{\prime}}\delta_{i}^{2}X_{i}X_{i}^{\top}$
$\displaystyle\preceq\frac{2(1+2\epsilon)}{|G^{\prime}|}\sum_{i\in
G^{\prime\prime}}\left\langle
X_{i},\theta-\theta^{\star}\right\rangle^{2}X_{i}X_{i}^{\top}+3\sigma^{2}\boldsymbol{\Sigma}^{\star}$
$\displaystyle\preceq
2(1+2\epsilon)C_{\textup{est}}L\left(\left\lVert\theta-\theta^{\star}\right\rVert^{2}_{\boldsymbol{\Sigma}^{\star}}+\sigma^{2}\right)\mathbf{I}\;.$

where the last line follows from (36). By suitably adjusting the choice of
$C_{\textup{est}}$, this proves that (8) is satisfied for this choice of
$G^{\prime\prime}$. Finally, we claim that (8) implies (7) via standard
techniques from the robust mean estimation literature, e.g. in the proof of
Lemma 3.2 in [DHL19]. ∎

###  A.2 Proof of Proposition 5

In this section, we state $\mathsf{FastCovFilter}$ and prove Proposition 5,
restated for convenience.

See 5

Algorithm 7 $\mathsf{FastCovFilter}(\mathbf{V},w,\delta,R)$

1: Input: $\mathbf{V}:=\\{v_{i}\\}_{i\in[n]}\in\mathbb{R}^{n\times d}$,
saturated weights $w\in\Delta^{n}$ with respect to bipartition $[n]=G\cup B$
with $|B|=\epsilon n$ for sufficiently small $\epsilon$, $\delta\in(0,1)$,
$R\geq\left\lVert\sum_{i\in
G}\frac{1}{|G|}v_{i}v_{i}^{\top}\right\rVert_{\textup{op}}$

2: Output: With probability $\geq 1-\delta$, saturated $w^{\prime}$ with
respect to bipartition $G\cup B$, with
$\left\lVert\sum_{i\in[n]}w^{\prime}_{i}v_{i}v_{i}^{\top}\right\rVert_{\textup{op}}\leq
5R.$

3: Remove all $i\in[n]$ with $\left\lVert v_{i}\right\rVert_{2}^{2}\geq nR$,
$n\leftarrow$ new dataset size

4: $T\leftarrow O(\log^{2}n)$ (for a sufficiently large constant),
$t\leftarrow 0$, $w^{(0)}\leftarrow w$

5: while $t<T$ and
$\mathsf{Power}\left(\sum_{i\in[n]}w^{(t)}_{i}v_{i}v_{i}^{\top},\frac{\delta}{2T}\right)>2R$
do

6: $\mathbf{M}_{t}\leftarrow\sum_{i\in[n]}w^{(t)}_{i}v_{i}v_{i}^{\top}$,
$\mathbf{Y}_{t}\leftarrow\mathbf{M}_{t}^{\log d}$

7: Sample $N_{\textup{dir}}=O(\log\frac{n}{\delta})$ (for a sufficiently large
constant) vectors $\\{u_{j}\\}_{j\in[N_{\textup{dir}}]}\in\mathbb{R}^{d}$ each
with independent entries $\pm 1$. Let
$\tilde{u}_{j}\leftarrow\mathbf{Y}_{t}u_{j}$ for all $j\in[N_{\textup{dir}}]$.

8: for $j\in[N_{\textup{dir}}]$ do

9: $\tau_{i}\leftarrow\left\langle v_{i},\tilde{u}_{j}\right\rangle^{2}$ for
all $i\in[n]$

10: $\tau_{\max}\leftarrow\max_{i\in[n]\mid w_{i}\neq 0}\tau_{i}$

11: while $\sum_{i\in[n]}w^{(t)}_{i}\tau_{i}\geq
2R\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}$ do

12:
$w_{i}^{(t)}\leftarrow\left(1-\frac{\tau_{i}}{\tau_{\max}}\right)w_{i}^{(t)}$
for all $i\in[n]$

13: end while

14: end for

15: $w^{(t+1)}\leftarrow w^{(t)}$, $t\leftarrow t+1$

16: end while

17: return $w^{(t)}$

Before proving Proposition 5, we require three helper facts.

######  Fact 3 (Theorem 1, [MM15]).

For any $\delta\in(0,1]$ and $\mathbf{M}\in\mathbb{S}_{\geq 0}^{d}$, there is
an algorithm, $\mathsf{Power}(\mathbf{M},\delta)$, which returns with
probability at least $1-\delta$ a value $V$ such that
$\lambda_{\textup{max}}(\mathbf{M})\geq V\geq
0.9\lambda_{\textup{max}}(\mathbf{M})$. The algorithm costs
$O(\log\frac{d}{\delta})$ matrix-vector products through $\mathbf{M}$ plus
$O(d\log\frac{d}{\delta})$ additional runtime.

######  Fact 4 (Lemma 7, [JLT20]).

Let $\mathbf{A},\mathbf{B}\in\mathbb{S}_{\geq 0}^{d}$ with
$\mathbf{A}\succeq\mathbf{B}$, and $p\in\mathbb{N}$. Then
$\textup{Tr}(\mathbf{A}^{p-1}\mathbf{B})\geq\textup{Tr}(\mathbf{B}^{p})$.

######  Fact 5.

For any $\alpha\geq 0$ and $\mathbf{A}\in\mathbb{S}_{\geq 0}^{d}$,

$\alpha\textup{Tr}(\mathbf{A}^{2\log d})\leq\textup{Tr}(\mathbf{A}^{2\log
d+1})+d\alpha^{2\log d+1}.$

###### Proof.

Every eigenvalue $\lambda$ of $\mathbf{A}$ is either at least $\alpha$ (and
hence $\lambda^{2\log d+1}\geq\alpha\lambda^{2\log d}$) or not (and hence
$\alpha^{2\log d+1}\geq\alpha\lambda^{2\log d}$). Both of these cases are
accounted for by the right hand side. ∎

###### Proof of Proposition 5.

We discuss correctness, runtime, and the failure probability separately.

Correctness. First, Line 3 is correct because these indices cannot belong to
$G$ as they would certify a violation to the operator norm bound in the
direction of $v$, so this preserves saturation. Next, it is clear by Fact 3
that if the algorithm ever ends because $\mathsf{Power}$ returns too small a
number, the output is correct, so it suffices to handle the other case. Define
the potential function $\Phi_{t}:=\textup{Tr}(\mathbf{Y}_{t}^{2})$. Our main
goal is to show that in every iteration the algorithm runs, $\Phi_{t}$
decreases substantially. To this end, we claim that after all runs of Lines
8-14 of $\mathsf{FastCovFilter}$ have finished, we have in all randomly
sampled directions $j\in[N_{\textup{dir}}]$ the guarantee

$\left\langle\tilde{u}_{j}\tilde{u}_{j}^{\top},\sum_{i\in[n]}w_{i}^{(t)}v_{i}v_{i}^{\top}\right\rangle\leq
2R\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}.$ (37)

This is immediate from the termination condition on Line 11 for each
$j\in[N_{\textup{dir}}]$, the fact that weights are monotone nonincreasing
throughout the whole algorithm, and that the left hand side of (37) is
monotone nonincreasing as a function of the weights. Next, by the Johnson-
Lindenstrauss lemma of [Ach03], for a sufficiently large $N_{\textup{dir}}$
with probability at least $1-\frac{\delta}{4T}$,

$\frac{1}{N_{\textup{dir}}}\sum_{j\in[N_{\textup{dir}}]}\left\langle
v_{i},\tilde{u}_{j}\right\rangle^{2}=\frac{1}{N_{\textup{dir}}}\sum_{j\in[N_{\textup{dir}}]}v_{i}^{\top}\mathbf{Y}_{t}\tilde{u}_{j}\tilde{u}_{j}^{\top}\mathbf{Y}_{t}v_{i}\in[0.95,1.05]\left\langle
v_{i}v_{i}^{\top},\mathbf{Y}_{t}^{2}\right\rangle\text{ for all }i\in[n].$

Condition on this event for all runs of Lines 8-14 throughout the algorithm
for the remainder of the proof. Combining this guarantee with (37), we have
that after Lines 8-14 terminate,

$\displaystyle\left\langle\mathbf{Y}_{t}^{2},\sum_{i\in[n]}w^{(t)}_{i}v_{i}v_{i}^{\top}\right\rangle$
$\displaystyle=\sum_{i\in[n]}w_{i}^{(t)}\left\langle
v_{i}v_{i}^{\top},\mathbf{Y}_{t}^{2}\right\rangle$
$\displaystyle\leq\frac{1.1}{N_{\textup{dir}}}\sum_{j\in[N_{\textup{dir}}]}\sum_{i\in[n]}w_{i}^{(t)}\left\langle
v_{i},\tilde{u}_{j}^{2}\right\rangle$
$\displaystyle=\frac{1.1}{N_{\textup{dir}}}\sum_{j\in[N_{\textup{dir}}]}\left\langle\tilde{u}_{j}\tilde{u}_{j}^{\top},\sum_{i\in[n]}w_{i}^{(t)}v_{i}v_{i}^{\top}\right\rangle\leq\frac{2.2R}{N_{\textup{dir}}}\sum_{j\in[N_{\textup{dir}}]}\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}.$

Next, by the Johnson-Lindenstrauss lemma of [Ach03], since all
$\\{u_{j}\\}_{j\in[N_{\textup{dir}}]}$ were sampled independently of
$\mathbf{M}_{t}$, we have with probability at least $1-\frac{\delta}{4T}$ that

$\frac{1}{N_{\textup{dir}}}\sum_{j\in[N_{\textup{dir}}]}\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}=\frac{1}{N_{\textup{dir}}}\sum_{j\in[N_{\textup{dir}}]}u_{j}^{\top}\mathbf{Y}_{t}^{2}u_{j}\leq
1.1\textup{Tr}(\mathbf{Y}_{t}^{2}).$

Conditioning on this event in every iteration, at the start of the next
iteration, we will have

$\left\langle\mathbf{Y}_{t}^{2},\mathbf{M}_{t+1}\right\rangle\leq
2.5R\textup{Tr}(\mathbf{Y}_{t}^{2}).$ (38)

We now show how (38) implies a rapid potential decrease:

$\displaystyle\Phi_{t+1}$
$\displaystyle=\textup{Tr}\left(\mathbf{M}_{t+1}^{2\log
d}\right)\leq\frac{1}{2.8R}\textup{Tr}\left(\mathbf{M}_{t+1}^{2\log
d+1}\right)+d(2.8R)^{2\log d}$
$\displaystyle\leq\frac{1}{2.8R}\textup{Tr}\left(\mathbf{Y}_{t}^{2}\mathbf{M}_{t+1}\right)+d(2.8R)^{2\log
d}\leq 0.9\Phi_{t}+d(2.8R)^{2\log d}.$

In the first inequality, we used Lemma 5 with $\alpha=2.8R$; in the second, we
used Fact 4 with $\mathbf{A}=\mathbf{M}_{t}$, $\mathbf{B}=\mathbf{M}_{t+1}$,
and $p=2\log d+1$. The last inequality applied (38). The above display implies
that until $\Phi_{t}\leq 20d(2.8R)^{2\log d}$, the potential is decreasing by
a constant factor every iteration, and $\Phi_{0}\leq
d\lambda_{\textup{max}}(\mathbf{M}_{0})^{2\log d}\leq d(nR)^{2\log d}$, so
within $O(\log^{2}n)$ iterations we will have

$\Phi_{t}=\textup{Tr}(\mathbf{M}_{t}^{2\log d})\leq 20d(2.8R)^{2\log d}.$

At this point, it is clear the operator norm of $\mathbf{M}_{t}$ achieves the
desired bound of $5R$. It remains to show that all weight removals in Lines
11-13 were safe throughout the algorithm. Here we use Lemma 1: it suffices to
show that throughout the algorithm,

$\sum_{i\in G}w_{i}^{(t)}\tau_{i}\leq
R\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2},$ (39)

because then whenever Line 11 fails, the scores are safe with respect to the
weights and Lemma 1 applies. However, (39) follows from the assumption on
$\left\lVert\sum_{i\in
G}\frac{1}{|G|}v_{i}v_{i}^{\top}\right\rVert_{\textup{op}}$, yielding

$\sum_{i\in G}w_{i}^{(t)}\tau_{i}\leq\sum_{i\in
G}\frac{1}{|G|}\tau_{i}=\left\langle\tilde{u}_{j}\tilde{u}_{j}^{\top},\sum_{i\in
G}\frac{1}{|G|}v_{i}v_{i}^{\top}\right\rangle\leq
R\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}.$

Runtime. The cost of all lines other than Lines 6-7 and the repeated loops of
Lines 11-13 clearly fall within the budget. To implement Lines 6-7, we never
need to form the matrices $\mathbf{M}_{t}$ or $\mathbf{Y}_{t}$, and instead
form all $\\{\tilde{u}_{j}\\}_{j\in[N_{\textup{dir}}]}$ in time

$O\left(nd\log d\log\frac{n}{\delta}\right)$

implicitly through matrix-vector multiplications with $\mathbf{M}_{t}$, each
of which take time $O(nd)$. To implement Lines 11-13, let $\bar{w}$ denote the
value of $w^{(t)}$ right after an execution of Line 10. We wish to determine
the smallest value $K$ such that

$\sum_{i\in[n]}\left(1-\frac{\tau_{i}}{\tau_{\max}}\right)^{K}\bar{w}_{i}\tau_{i}\leq
2R\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}.$

Checking if the above display holds for a particular guess of $K$ clearly
takes $O(n)$ time, and we can upper bound $K$ by the following inequality:

$\displaystyle\sum_{i\in[n]}\left(1-\frac{\tau_{i}}{\tau_{\max}}\right)^{K}\bar{w}_{i}\tau_{i}\leq\sum_{i\in[n]}\exp\left(-\frac{K\tau_{i}}{\tau_{\max}}\right)\bar{w}_{i}\tau_{i}\leq\frac{1}{eK}\sum_{i\in[n]}\bar{w}_{i}\tau_{\max}\leq\frac{\tau_{\max}}{K}.$

Here the second inequality used $x\exp(-Cx)\leq\frac{1}{eC}$ for all
nonnegative $x$, $C$, where we chose $C=\frac{K}{\tau_{\max}}$ and
$x=\tau_{i}$. Now since
$\tau_{\max}\leq\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}\left\lVert
v_{i}\right\rVert_{2}^{2}\leq nR\left\lVert\tilde{u}_{j}\right\rVert_{2}^{2}$
by Cauchy-Schwarz, we have that $K=O(n)$ as desired. At this point, a binary
search on $K$ suffices, so all loops take time $O(n\log n)$.

Failure probability. The only randomness used in the algorithm appears in the
guarantees of $\mathsf{Power}$ and the guarantees of the Johnson-Lindenstrauss
projections. Taking a union bound over $T$ iterations shows these all succeed
with probability at least $1-\delta$. ∎


Remi Brochenin1 Joos Buijs1 Mehrnoosh
Vahdat2 Wil van der Aalst1
Brochenin et al.

Department of Mathematics and Computer Science,
Eindhoven University of Technology, 5612AZ Eindhoven, The Netherlands,
Department of Industrial Design,
Eindhoven University of Technology, 5612AZ Eindhoven, The Netherlands

{r.brochenin, j.c.a.m.buijs, m.vahdat<EMAIL_ADDRESS>
Resource Usage Analysis from a Different Perspective on MOOC Dropout
Resource Usage Analysis