TITLE: Acceptors with very high energy level in semiconductor
QUESTION [0 upvotes]: I have gallium arsenide (energy gap of 1.4 eV) doped with silicon in concentration of $10^{14} cm^{-3}$ and energy level very close to the conduction band so it's act like a donor. Now we put in also chromium with concentration of $10^{17}cm^{-3}$ that act like accepotr. The problem is that the energy level of the chromium is in the middle of the bang gap, so the thermal energy is not enough to create holes in the valence band. Now i need to calculate the conductivity and mobility but i don't understand how the chromium effect them, from my understanding he has no effect on the conductivity because they are very far from valence band.
Any idea?

REPLY [0 votes]: The deep chromium acceptors take away electrons from the silicon donors. As they outnumber the donors there will be no charge carriers left except for a very small number, due to thermal ionisation of the deep acceptors and E en fewer intrinsic electrons and holes. The material will have very low conductivity.


TITLE: Determining if a limit does not exist.
QUESTION [3 upvotes]: I am having trouble determining if the limit defined below exists. I do not believe it does, but I am not sure how to find 2 paths where the limits differ. I've tried $f(x, mx)$, $f(my, y)$, $f(x, mx^2)$, but nothing really seems to work.
Show that the limit does not exist:
$$
\lim_{(x,y) \to (0,0)} \frac{y^2 + (1-\cos(x))^2}{x^4 + y^2}
$$
I thought about parameterizing using polar coordinates, but I wasn't sure how to show that the $\displaystyle \lim_{r^+ \to 0}$ will depend on $\theta$ (and hence does not exist).
Any help appreciated. Thanks.

REPLY [1 votes]: Since
$1-\cos(x)
=2\sin^2(x/2)
$,
since
$\sin x \approx x$
as $x \to 0$,
$\frac{y^2 + (1-\cos(x))^2}{x^4 + y^2}
=\frac{y^2 + 4\sin^4(x/2)}{x^4 + y^2}
\approx \frac{y^2 + x^4/4}{x^4 + y^2}
$.
We can now apply a
standard technique
and let
$y = k x^2$.
This becomes
$\frac{k^2x^4 + x^4/4}{x^4 + k^2x^4}
=\frac{k^2 + 1/4}{k^2+1}
$
which will have
different values
for different values
of $k$.


TITLE: Finding the Taylor Series Approximation of $\sin(x)$ at $x=\pi/4$
QUESTION [1 upvotes]: I'm trying to find a Taylor series approximation for $\sin(x)$ at $\pi/4$.
Simply going through the derivatives, I get:
\begin{align}
f(\pi/4) &= \frac{1}{\sqrt{2}}\\
f'(\pi/4) &= \frac{1}{\sqrt{2}}\\
f''(\pi/4) &= -\frac{1}{\sqrt{2}}\\
f^{(3)}(\pi/4) &= -\frac{1}{\sqrt{2}}\\
f^{(4)}(\pi/4) &= \frac{1}{\sqrt{2}}
\end{align}
Using the Taylor series approximation formula (http://upload.wikimedia.org/math/c/3/a/c3a379aaf2b04999084373279ed2da10.png), do I simply sub in pi/4 wherever I see an a?
WolframAlpha solved it like this: http://i.imgur.com/LN8SW0b.png so I'm probably doing something wrong.

REPLY [1 votes]: You've calculated the derivatives correctly; so yes, you would just substitute in $\frac{\pi}4$ wherever you see an $a$. This would yield, as the start of the sum:
$$\sin(x)=\frac{1}{\sqrt{2}}+\frac{x-a}{\sqrt{2}}-\frac{(x-a)^2}{\sqrt{2}\cdot 2!}-\frac{(x-a)^3}{\sqrt{2}\cdot 3!}+\frac{(x-a)^4}{\sqrt{2}\cdot 4!}+\ldots$$
What Wolfram|Alpha is doing is, to get the proper alternation of signs in the terms (i.e. +, +, -, -, +, +, -, -, ...) is using the term $\sqrt{2}\sin(\frac{1}4(\pi+2n\pi))$ (though it cancelled the $\sqrt{2}$ with the one in the denominator of your expansion) which, as $n$ increases yields the sequence $1$, $1$, $-1$, $-1$, $1$, $1$, \ldots


TITLE: Which derivation of drift velocity is correct?
QUESTION [14 upvotes]: In the derivation of drift velocity I have seen two variations and want to know which one's correct.

$s=ut+\frac{at^2}{2}$
Assume that the drift velocity of any electron in any conductor is :
$$\vec{v_d}=\frac{\vec{l}}{t}$$
Due to the electric field the acceleration of electrons in any conductor is:
$$a=\frac{-e\vec{E}}{m}$$
Now the distance travelled by an electron after a long time (initial thermal velocity = 0)
$$l=\frac{at^2}{2}\implies \frac{-e\vec{E}t^2}{2m}$$
the time between the collisions is $\tau$ $\therefore$ $$l=\frac{-e\vec{E}\tau^2}{2m}$$
thus the velocity is $$\vec{v_d}=\frac{-e\vec{E}\tau}{2m}$$
In another proof I saw the author using $v=u+at \implies v_d=\frac{-e\vec{E}\tau}{m}$

My question is which of the the two equations of motion can be used in the proof? Can they be used at all.

REPLY [19 votes]: The values you give for the drift velocity are from a primitive approximation, which does not correctly take into account the statistical nature of the motion. The collision does not randomize the velocity immediately, nor is it true that there are discrete collisions, the collisions of a classical particle in a dense medium happen more or less continuously, as the particle shoves others, and this jostling is not easy to describe.
So the velocity you get from these equations are order of magnitude estimates only, they are not supposed to be taken too seriously, they only give you a rough seat-of-the-pants idea of how the charged particles move. In this sense, the two answers are the same, because the only differ by a factor of 2. Neither one is correct.
It is important to say immediately that this classical seat-of-the-pants idea is completely wrong for electrons in metals, it is only approximately valid for something like ionic conduction, for example, conducting current in salt water by drifting Na+ and Cl- ions in solution, depositing on the two electrodes. It is also more valid when the particles are larger, like charged molecular ions in solution, much bigger than water molecules. The motion of electrons in metals is highly quantum, the electrons make a cold Fermi gas, and this gas can't be described in any way by classical biased thermal drift, not even as a crude approximation.
But for large-molecule ionic conduction, the classical random-drift model is correct, since at room temperature, the motion of ions in solution is classical. Within this model, it is appropriate to ask whether the drift velocity of ions is equal to $ {e\over m} \tau E$ or half this value, or twice this value.
But to give an answer, you need a better definition of the parameter $\tau$ than "the mean time between collisions". This definition is only ok for intuition and for order-of-magnitude estimates. The proper definition of $\tau$ is as the relaxation rate of the velocity, the exponential decay rate of information about the velocity of the ion in time. If you have a velocity $v$ on the ions, it tells you how the ion velocity randomizes.
The only reason that such a parameter exists is because the random collision process of a classical ion (or any classical particle in a thermal background) can be well described by a stochastic equation. This was discovered by Einstein and Smoluchowski in 1905. Stochastic equations are usually considered somewhat more advanced than the elementary description in terms of mean free path, but they are the only way to answer a question about factors, like your question, where a mean-free-path description is inadequate.
In a stochastic description, you assume that you have a probability distribution of the ion's velocity at the initial time, and you ask how the probability distribution changes in time, over a time-scale long compared to the collision time. The equation that tells you this is a partial differential equation known as the Fokker Planck equation:
$$ {\partial_t \rho(v)} = -\partial_x ( D\partial_x\rho - {1\over\tau} v \rho) $$
The meaning of this equation can be clarified by thinking of it as a current equation: it is saying that when you have a probability density $\rho(v)$ at some velocity $v$, this probability density tends to move to smaller $v$ (the second term inside the parentheses on the right), with a time-constant $\tau$, and if there is a gradient of probability, it tends to smooth out by diffusion (the first term on the right).
To solve for the stationary distribution, you make the probability current zero,
$$ D\partial_v \rho - {1\over \tau} v \rho = 0$$
$$ \rho \propto e^{- v^2\over 2\tau D} $$
But we know from general principles of statistical mechanics that the stationary distribution for particle velocities should be the Maxwell distribution, which is also a Gaussian:
$$ \rho \propto e^{-mv^2\over 2kT}$$
And this leads to an Einstein relation:
$$ {1\over \tau D} = {m\over 2kT} $$
so that knowing $\tau$ determines the velocity diffusion constant $D$:
$$ D = {2kT \tau \over m} $$
This tells you the relationship between the rate at which the velocity decays (forgets its initial value) and the parameter $D$, which tells you how the velocity randomizes.
If you apply a force to the ions, you get an extra drift in the probability current:
$$ \partial_t \rho = \partial_x( {2kT\tau\over m}\partial_x - {1\over\tau} v \rho + {F\over m}\rho) $$
You can find the new stationary distribution, and see that it is a Gaussian centered at a new velocity:
$$ \rho(v) \propto e^{ - {m(v-v_d)\over 2kT}} $$
From this, and the fact that the force on an ion is $qE$, you can find the drift velocity:
$$ v_d = {qE\tau \over m} $$
The parameter $\tau$ is therefore nothing more than the precise analog of the imprecise "time-to-collisions" parameter you give, and when a classical system obeys a Fokker Planck equation (which is usually), you find this relation.
There are no factors of 1/2 in this equation, which is why the reference you find does not give this. But the parameter $\tau$ is now defined differently--- it is not exactly the time until collisions, it is the relaxation rate of the velocity.
To understand this better, you can dimensionalize the equation: set the new time unit in the Fokker-Planck equation to be $\tau$, and the velocity unit to be (sqrt of 2 times) the thermal velocity $2\sqrt{kT\over m}$. Then the equation assumes the form:
$$ \partial_t \rho = \partial_v ({1\over 2} \partial_v\rho) - v\rho) $$
This equation can be mathematically turned into the imaginary time Schrodinger equation by writing:
$$ \rho(x) = e^{-v^2\over 2} \psi(x) $$
This gives:
$$ \partial_t \psi = - {1\over 2} \partial_v^2 \psi - (v^2 - {1\over 2}) \psi(v) $$
Which is the imaginary time Schrodinger equation for a "wavefunction" in $v$ (this is just a mathematical analogy which allows me to use the known eigenvalues of the SE, it isn't physics. It is justified by the fact that both equations are described by a path integral), with a Harmonic oscillator potential.
The energy levels of this Hamiltonian are the Eigenvalues of the differential operator, and they would give the energies in real time, but they give the decay rates in imaginary time. The change of variables from $\rho$ to $\psi$ doesn't affect eigenvalues, so that the Fokker-Planck equation in time has decay rates which are integers. So you learn that the decay rate is an integer multiple of the time unit $\tau$.
So the parameter $\tau$ has an interpretation as the natural decay rate of small perturbations to the Maxwell Boltzmann distribution. In this way, it is a natural generalization of the "time to first collision", it is the main parameter telling you how long before the velocity will randomize in thermal equilibrium.
Stochastic equation formulation
The above can be made more transparent if you allow yourself one somewhat more advanced concept, the concept of a white-noise function. A white noise $\eta(t)$ is the derivative of a Brownian motion. It is a function of time which is completely random at each time, so that it's integral over any interval is a Gaussian distributed random variable of variance equal to the width of the interval.
The best way to define this free of mathematical annoyances is to make time a fine lattice of spacing $\epsilon$, and then $\eta$ is independently random at each lattice point, with a probability distribution which is Gaussian centered at zero of width $1\over\sqrt{\epsilon}$.
$$\rho(\eta(x)) = e^{-{\eta(x)^2\over 2}\epsilon}$$
Multiplying the independent probability at each point, you get a sum in the exponent, and a probability distribution for each collection of possible values of the function $\eta$. I will replace the sum by an integral, since the $\epsilon$ is in the right place to do this.
$$ e^{-\int {\eta^2\over 2} dt }$$
In terms of this random noise, the equation of motion for a Brownian particle is very simple:
$$ m{dv\over dt} = -{m\over \tau} v + \sqrt{2D}\eta $$
That's it! It says that the velocity goes to zero according to a linear friction law, with time-constant $1\over \tau$, and also gets random kicks at each instant of time of size $\epsilon$, whose size is $\sqrt{2D\over\epsilon}$. The magnitude of the kicks is diverging at tiny $\epsilon$, but it is random in all directions, so that it mostly cancels out, and the average energy transfered to the particle in thermal equilibrium over a time $\tau$ is about $kT$ (in a random way). The statistical path-integral over $\eta$ reproduces the Fokker Planck equation in the same way that the path-integral of the Lagrangian in quantum mechanics reproduces the Schrodinger equation.
If you have an external force, you just add it to the right hand side:
$$ m{dv\over dt} = -{m\over \tau} v + qE + \sqrt{2D}\eta $$
The average value of v is the drift velocity, and it is found by taking a long-time average of this equation, where all terms vanish except the ones proportional to $v$, which become $v_d$, the averaged drift velocity:
$$ -{m\over\tau} v_d + qE = 0 $$
From this, you can read off your relation. You can see that the coefficient $\tau$ is the time-constant for a classical velocity to decay. You can also see that the statistical details are not important--- the important thing is that there is a long-time limit where the average of the random force is zero, and the average of the time-derivative of $v$ is also zero.
I will stop and justify the statement that the average of $\eta$ and ${dv\over dt}$ are both zero over long times. The average of $\eta$ is zero by definition--- it is a quantity whose average over a window of size T is proportional to $\sqrt{T}$. The average of $dv\over dt$ is the integral:
$$ {1\over T} \int_0^T dv = {v_f - v_i\over T} $$
and both the initial and final velocities are of the order of the thermal velocity, and are constant, while $T$ becomes long.
The stochastic equation formulation is the most natural for these types of problems.
Cold Fermi Gas
You asked about electrons, unfortunately, not charged pollen particles or charged ions in solution. For the case of electrons, this classical picture is completely inapplicable.
In this case, the electrons are moving in a quantum way, so that they have lattice wavenumbers $k$ and make a Fermi-Dirac distribution at temperature $T$ which only has a thin skin of wavenumbers near the fermi $k$ excited. It is only these electrons that participate in conduction.
When you apply a voltage, the electrons at wavenumbers near $k_f$ gain energy from the field, and lose energy by scattering, but the process is not classical at all, because the electrons cannot go to a state significantly smaller than $k_f$, because these states are occupied, and neither can they go to a state significantly higher than $k_f$, because $kT$ is much smaller than the Fermi energy in the system.
So these electrons are running around in quantum waves which are forced to have a definite velocity, and can only change direction in response to impurities and phonons. This scattering process gives rise to classical resistance, but to calculate this requires quantum mechanical treatment, and is a separate question from any classical velocity relaxation.


TITLE: what is the image of the disk?
QUESTION [2 upvotes]: Consider two infinite opaque walls(planes) A and B separated by a distance c; A light emitting disk of radius r is placed parallel to the floor at a distance d from the wall B. Now a hole is punched at a height of h from the floor. What shape is the image of the disk formed on wall A?

*this crude image shows the setup

I tried to write the "process" as a complex function.
I got $f(x,y) = \frac{xc}{y-h} +i\frac{yh}{y-c}$
 where x and y is the position of a point on the floor with respect to A...
I still can't find a reasonable expression for the image.

REPLY [3 votes]: HINT:
Place the center of coordinate system at the position of the hole. Now the horizontal plane has equation
$$H \colon z = - h$$
In this plane we have a circle of radius $r$ with center at the point $(r + d, 0, - h)$ ( if $d$ were $0$, then the circle touches the wall; in general it is at the distance $d$ to the right). The equation of the circle in this horizontal plane is
$$f(x,y) \colon = (x-(d+r))^2 + y^2 - r^2=0, \ \ z = -h$$
The equation of the cone determined by this curve is homogenous in $x$, $y$, $z$ ( that is, depends only on the ratios $\frac{x}{z}$, $\frac{y}{z}$, or $[x\colon y \colon z]$, and can be easily checked to be
$$f(\frac{-h x}{z}  , \frac{-h y}{z} ) = 0$$
Now to find the intersection of the cone with the vertical plane $x=-c$, plug in $x=-c$ in the above equation in $x$, $y$, $z$, and get an equation in $y$, $z$
$$f(\frac{-h (-c)}{z}, \frac{-h y}{z}) = 0$$
$\bf{Added:}$ Let's consider a numerical case: $h= 2$, $c = 3$, $d=1$, $r = 4$.
The equation of the circle in the horizontal plane $z= -2$ is
$$(x-(1+4))^2 + y^2 - 16 = 0$$
or
$$x^2 - 10 x + y^2 + 9 = 0$$
Now homogenize ( $x \mapsto \frac{-2 x}{z}$, $y\mapsto \frac{-2y}{z}$) and get the equation of the cone
$$4 x^2 + 20 x z + 4 y^2 + 9 z^2 = 0$$
Now plug in $x=- 3$ in the above.
$\bf{Added:}$ Explanation for the equation of the cone:  along a ray of the cone all of the points  have proportional coordinates. Hence the equation of the cone has to be of the form $F(\frac{x}{z}, \frac{y}{z})= 0$. Now the idea is to obtain an equation of this form from the equation $f(x,y)=0, \ \ z=-h$.  Substitute  $x$ with $\frac{-h}{z} \cdot x$ ( note that the fraction is $1$ on the plane $z=-h$), and similarly for $y$.


TITLE: How can vorticity tilt?
QUESTION [1 upvotes]: Most descriptions of tornado genesis make a reference to vorticity at the ground level with a horizontal axis somehow tilting to the vertical. Why doesn't this violate conservation of angular momentum?

REPLY [2 votes]: A vortex in a uniform flow field will not tilt, it will stay as it is aligned and move along with the flow. However, if there is a gradient in the velocity field, this can cause a vortex to stretch and/or tilt.
To get math-y first... if we take the equation for the velocity of a fluid and we take the curl of that equation, we get what is called the vorticity equation. This equation is an expression of the conservation of (local) angular momentum. If we assume the fluid is incompressible (which just makes the equation simpler to look at by removing some terms, but it doesn't change what we're talking about here), we get:
$$ \frac{D \vec{\omega}}{Dt} = (\vec{\omega} \cdot \nabla) \vec{u} + \nu \nabla^2 \vec{\omega} $$
where $\vec{\omega}$ is the vorticity. The second term on the right hand side is the viscous dissipation of vorticity. The first term on the right hand side is the stretching/tilting of a vortex due to velocity gradients.
Let's look at what would make a horizontal vortex tilt to a vertical one like a tornado would. Let's assume that our ground plane is in the X-Y direction and our altitude (vertical) direction is in Z. A horizontal vortex that is up in the clouds would be the X-component of vorticity, $\omega_x$. A vertical vortex like a tornado would be the Z-component of vorticity, $\omega_z$.
Let's write out those two specific equations to see how they might interact. We are only interested in the tilting, so let's ignore viscosity for the moment. The horizontal vortex equation looks like:
$$ \frac{D \omega_x}{Dt} = \omega_x \frac{\partial u_x}{\partial x} + \omega_y \frac{\partial u_x}{\partial y} + \omega_z \frac{\partial u_x}{\partial z} $$
and the vertical equation looks like:
$$ \frac{D \omega_z}{Dt} = \omega_x \frac{\partial u_z}{\partial x} + \omega_y \frac{\partial u_z}{\partial y} + \omega_z \frac{\partial u_z}{\partial z} $$
Now, let's assume that we start out with no vertical vorticity -- no tornado like behavior, just a big horizontal one. This means the initial $\omega_y$ and $\omega_z$ are zero. If we simplify the equations, we get:
$$ \frac{D \omega_x}{Dt} = \omega_x \frac{\partial u_x}{\partial x} $$
$$ \frac{D \omega_z}{Dt} = \omega_x \frac{\partial u_z}{\partial x} $$
Okay -- so what does this tell us. Well, first it tells us that the horizontal vorticity (initially) will increase or decrease as it gets stretched or squeezed along the axis of the vortex. If you stretch it, the vortex gets smaller in diameter and vorticity increases -- this is the "spinning figure skater pulling in their arms and speeding up" effect. The opposite happens if you squish it -- it gets wider and spins slower.
The second equation tells us that the vertical vortex will start to increase due to gradients in the vertical velocity along the horizontal direction. In weather, this means there is an updraft of down-draft. In other words, you have horizontal blowing wind that turns upwards and creates gradients in the vertical velocity along the axis of the tornado. This will cause the vortex to start tilting, and turns the horizontal vorticity into vertical vorticity.
During this tilting process, vorticity (and angular momentum) is still conserved, it is just re-arranged between components. So the vorticity in the horizontal direction will decrease, vorticity in the vertical will increase, and it is all driven by gradients in the velocity aligned with the vortex itself.

Just to complete the picture, once the vortex starts to tilt and we have both X and Z components of vorticity, the equations becomes:
$$ \frac{D \omega_x}{Dt} = \omega_x \frac{\partial u_x}{\partial x} + \omega_z \frac{\partial u_x}{\partial z} $$
$$ \frac{D \omega_z}{Dt} = \omega_x \frac{\partial u_z}{\partial x} + \omega_z \frac{\partial u_z}{\partial z} $$
and this shows the interchange between vorticity components based on the velocity field. It is obviously a dynamic system so it isn't obvious how it all plays out, but an updraft will cause the horizontal vortex to start to tilt towards the vertical, making a tornado start to form. Then, once you have some vertical vorticity $\omega_z \neq 0$, that vortex can get stronger or weaker due to stretching (faster spin, smaller diameter) or squeezing (slower spin, larger diameter) caused by $\frac{\partial u_z}{\partial z}$ -- i.e. due to acceleration or deceleration of the updraft along the axis of the tornado, respectively.

REPLY [1 votes]: A tornado is not an isolated system and may exchange angular momentum with the Earth and with the non-tornado parts of Earth’s atmosphere.


TITLE: If $f,g \in \mathscr{R[a,b]}$ , then $\sqrt{f^2+g^2}\in \mathscr{R[a,b]}$
QUESTION [1 upvotes]: Show that if $f,g: [a,b] \rightarrow \mathbb{R}$ are Riemann integrable  then $\sqrt{f^2+g^2}$ is Riemann integrable and
$\int_a^b \sqrt{f^2 + g^2} dx \leq \int_a^b |f| dx + \int_a^b |g| dx$

So I'll start by writing down what I know:
I know by arithmetic of integrals that $|\int_a^b fg dx| \leq \sqrt{\int_a^b f^2} dx \cdot \sqrt{\int_a^b g^2 dx}$.
I also know that the function will be RI iff: $\exists P=\{a=x_0, x_1, ... , x_n = b\} \text{ a partition}$ s.t $U(f,p) - L(f,p) < \epsilon$. Finally, if f is any bounded function then $\overline{\int} f dx \geq \underline{\int} f dx$.
And so to prove Riemann integrability I'm guessing we let choose partitions such that:
$U(f,p_1) - (\text{ some } \epsilon ) < \int_a^b fdx < L(f,p_1) + (\text{ some } \epsilon)$. Similarly for $p_2$.
Let $P = P_1 \cup P_2$ band let $x,y \in [X_{i-1}, x_i]$ for some $1 \leq i \leq N$. And so we're left with
$\sqrt{(f^2(x) + g^2(x)) - ((f^2(y)-g^2(y))}$
I know I'm supposed to show that the above is less than something, and do an $\epsilon$ argument, but I really can't figure it out.
As for proving the inequality,
$\sqrt{U(f^2+g^2,p)} \leq \sqrt{\sum \sup f^2+g^2 \Delta x_i}$
And again, I don't know how to proceed.
Help would be much appreciated!

REPLY [1 votes]: Use Lebesgue criterion: $\sqrt{f^2+g^2}\le\lvert f\rvert+\lvert g\rvert$, which is bounded, and the discontinuities of $\sqrt{f^2+g^2}$ are a subset of the union of discontinuities of $f$ and $g$, which is a set of zero-measure.
BTW, it is superfluous to say that $f$ and $g$ are bounded. If they are Riemann integrable on a closed interval, they are automatically bounded.


TITLE: Subsets of a set of points that can lie in the same sphere
QUESTION [7 upvotes]: Suppose I have a finite set $\mathcal{P} := \{x_1, x_2, \ldots , x_n\} \subset \mathbb{R}^d$.
Is there any way to characterize the couples $(x_i, x_j)$ such that there exists a ball $B$ with $x_i, x_j \in B$ but all the other points in $\mathcal{P}$ are not inside $B$.
Some obvious remarks on the question :
$\bullet$ For any point $x_i$, take the point $x_j$ that is closest to $x_i$, then $(x_i, x_j)$ verifies the desired property.
$\bullet$ For a couple $(x_i, x_j)$, if there exists an $x_k$ on the segment joining the two points, then $(x_i, x_j)$ cannot verify the property.
$\bullet$ It also seems that the edges between "adjacent extremal points of the convex hull'' (I don't know how to call these) always satisfy the property, as we may take a sphere with a centre far away.
This shows that this property is not really trivial. I have made a small approximate figure in the plane here, with the green edges representing the edges satisfying my problem (I only have an online drawing tool available :) ):

I am really looking for any necessary and/or sufficient condition, or reference if this has a name. Of course a partial answer on the plane would be nice already.
My further objective is to get a necessary and sufficient condition for the same property but for more than two points, and to impose that the center of the sphere lies outside the convex hull of the points.

REPLY [1 votes]: I'll assume we're working in $\mathbb{R}^2,$ though I think the idea works in $\mathbb{R}^n$ with modifications.
If $(x_i,x_j)$ verifies the property for a ball $B,$ then if $B$ can be replaced by another ball $B'$ where $B' \subseteq B,$ $(x_i,x_j)$ will also verify the property for the ball $B'.$ This means we may assume that each of $x_i,x_j$ lies on the bounding circle of $B.$ For if initially both are interior to $B$ we may decrease the radius of $B$ keeping its center fixed until the furthest from center of $x_i,x_j$ (say $x_i$) lies on the bounding circle, and then if $x_j$ is still in the interior we may move the center of $B$ along the segment joining its center at that stage to the boundary point $x_i$ while keeping the bounding circle of $B$ passing through $x_i$, until such time as $x_j$ also lies on the bounding circle. In both changes of $B$ it has moved to subsets of itself.
Now consider any third point $x_k$ in the given set of points. If it happens that $x_k$ lies interior to the segment joining $x_i,x_j$ then $(x_i,x_j)$ does not verify the property (as noted by the OP). Secondly if $x_k$ happens to lie elsewhere on the line through $x_i,x_j$ then this $x_k$ will be outside the ball $B$ so has no effect on the question whether $(x_i,x_j)$ verifies the property.
Needed adjustment: In case the circle bounding ball $B$ through $x_i,x_j,x_k$ has all other points strictly outside it, then that $B$ does not verify the property for the pair $(x_i,x_j).$ However since all other points are at strictly positive distance from $B,$ the bsall $B$ may be adjusted slightly so as to have $x_i,x_j$ on its bounding circle but hsve $x_k$ and all remaining points strictly outside it.
Now the rest is a tedious computation which will end up deciding one way or the other if the pair $(x_i,x_j)$ verifies the property. For each fixed $x_k$ (not on the line through $x_i,x_j$) we form the circle through $x_i,x_j,x_k$ and check whether all the remaining points in our given finite set happen to lie  outside that circle. If any of these $x_k$ give all the remaining points outside its circle we can stop, and say that $(x_i,x_j)$ verifies the property. However if none of the $x_k$ tested has all remaining points outside the generated circle, we can say that $(x_i,x_j)$ does not verify the property.
I may need to elaborate on why the failure of all tested $x_k$ proves the pair $(x_i,x_j)$ does not verify the property. (Will return to this later if I can word that argument well.)


TITLE: What is this total length
QUESTION [0 upvotes]: What is the value of the total length of all the edges connecting the vertices of a regular $k$-gon that is inscribed
on a unit circle?

REPLY [1 votes]: (This tells you exactly what to do, and I left some minor computation for you.)
First, we assume that $k$ is odd, and $k = 2n + 1$. For any integer $ 1 \leq i \leq n$, there are $k$ pairs of vertices that are length $i$ apart. Since the central angle is $\frac{2i\pi}{n}$, their distance is $2 \sin \frac{i\pi}{n}$. Hence, the sum of distances is
$$k \sum_{i=1}^n 2 \sin \frac{i\pi}{n}, $$
which you should recognize as a telescoping trigonometric sum, and can simplify to a closed form.
The case $k=2n$ is even is dealt similarly, just that there are only $n$ pairs of vertices that are $n$ vertices apart.


TITLE: Existence and uniqueness of SDE, is the independence requirement needed?
QUESTION [2 upvotes]: In Bernt Øksendals Stochastic differential equations he has this theorem in chapter 5:

$\\\\\\$
However, in the proof I can not see where he uses the independence condition I marked in red. Do you know if this theorem also holds if we do not assume independence? The proof is long, so I might have missed where he uses it. So do you know if the theorem holds without this? If you are familiar with the proof, do you see where he uses this condition?
$\\\\\\$

reference: http://th.if.uj.edu.pl/~gudowska/dydaktyka/Oksendal.pdf
chapter 5.2

REPLY [5 votes]: On the right side of the case $k=0$ of formula (5.1.12) you have the Ito integral $\int_0^t\sigma(s,Z)\,dB_s$. For this to make sense we need $B$ to be a Brownian motion with respect to the filtration $(\mathcal F^Z_t)$, and the simplest way to ensure this is to assume that $Z$ is independent of $B$.


TITLE: Residue Theorem with Fractional zeros
QUESTION [1 upvotes]: i'm just running through a problem, the example i have been given isn't extensive and so i'm trying to extrapolate from that. any help would be greatly appreciated.
Calculate
$$g(z)=\int_0^\infty \frac{x^{\frac{1}{4}}}{x^3+1} \, dx$$
Now, i recognise this as an integral of the type
$$\int_0^\infty x^{\alpha-1} f(x) \, dx$$ which we can move into the complex plane with $f$ is a rational function such that $f(\mathbb{R}) \subseteq \mathbb{R}$. $g$ is analytic on $\mathbb{C}$ with the exception of the finite points $\{-1, \frac{1-i\sqrt{3}}{2},\frac{1+i\sqrt{3}}{2}\}$ none of which are in $[0,\infty)$ and $a \in \mathbb{R} \setminus \mathbb{Z}$ (it's obvious to see that $a = \frac{5}{4}$
now we assume that there exists constants $R>0,M_1>0 \text{ and } \delta_1>0$ such that
$$|f(z)z^{\alpha-1}|\leq \frac{M_1}{|z|^{1+\delta_1}},~|z|>R, \tag 1
$$
and constants $r>0,M_2>0 \text{ and } \delta_2>0$ such
$$|f(z)z^{\alpha-1}| \leq M_2|z|^{\delta_2-1}, \tag 2$$
now we consider
$$z^{\alpha - 1}=z^{\frac{1}{4}}$$ and $$f(z) = \frac{1}{z^3+1}$$
then the conditions of (1) and (2) works out to be, does
$$\frac{z^{\frac{5}{4}}}{z^3+1} \longrightarrow 0$$
as $z \longrightarrow 0$ and $z \longrightarrow \infty$
obviously as $z$ tends to zero we have $0,$ and $z^3$ outpaces $z^{\frac{5}{4}}$ and so we have $0$ on both accounts.
now....on to the integral.
$$\int_0^\infty \frac{z^{\frac{5}{4}}}{z^3+1} \, dz = \frac{2 \pi i}{1-e^{\frac{\pi i}{2} }}\left[ \operatorname{Res} \left(z^{\frac{1}{4}}f(z),-1\right) + \operatorname{Res} \left(z^{\frac{1}{4}}f(z),\frac{1-i\sqrt{3}}{2}\right) + \operatorname{Res} \left(z^{\frac{1}{4}}f(z),\frac{1+i\sqrt{3}}{2} \right)\right]-\frac{\left(\int_{S^{-}_{\epsilon}(0)} f(z) z^{\frac{1}{4}}+\int_{S^{+}_{\frac{1}{\epsilon}}(0)} f(z) z^{\frac{1}{4}}\right)}{1-e^{\frac{\pi i}{2}}}$$
now from my understanding this is the correct integral, i need to consider it as $\epsilon \longrightarrow 0$, now...one major issue i'm having is that i'm not understanding what the contour is in this instance, normally for $\pm \infty$ we just consider the upper half plane...are we considering only a single quarter in this instance?
I've seen solutions as both $$\frac{\pi}{3 \sin{(\frac{5 \pi}{12})}}$$ and
$$\frac{1}{3}\Gamma\left(\frac{5}{12}\right)\Gamma\left(\frac{7}{12} \right)$$
where
$$\Gamma(z) = \int_0^\infty x^{z-1}e^{-x} \, dx$$
which i believe are equivalent.
Any and all help would be great.

REPLY [1 votes]: First manipulate the real valued integral before you jump into the complex domain. Use the substitution $u^4=x$
$$\int_0^\infty \frac{x^{\frac{1}{4}}}{x^3+1}dx = \int_0^\infty \frac{4u^4}{u^{12}+1}du$$
Now there is no ambiguity with fractional powers.


TITLE: Probability over an infinite set. Of two numbers.
QUESTION [2 upvotes]: Suppose there is a man, who chooses two completely random numbers. So they can be equal too. And they can be only positive real numbers. One of them can even be $285294.38285967281$ or anything bizarre. So my question is, what is the probability that the first number is greater?
So I did it like this:
Probability of two numbers being equal would be $\frac{1}{\infty}$ and $\lim_{x\to\infty} \frac{1}{x}=0.$
And thus, our required probability, over an infinite space will be $\frac{1}{2}$.
But some of my fellow men are saying that probability theory cannot be extended over infinite space. But I totally disagree with them. Even, the infinite monkey theorem uses infinity. So am I right? Also one of my friends also told me that there is a way by the x-y plane. The areas of the two triangles formed on either sides of the line $y=x$ will be equal and a line doesn't have an area. So probability will be $\frac1{2}$.

REPLY [4 votes]: "Two completely random numbers" is not a well-defined probability distribution,
even when restricted to positive real numbers.
The actual probability distribution must be something more specific,
for example, if all positive real numbers are possible choices then the
exponential distribution
is a possibility.
But notice that with an exponential distribution, the probability of
choosing a number between $1000$ and $1001$ is less than
the probability of choosing a number between $1$ and $2$.
There is literally no possible random process with an infinite number of
possible outcomes that can have a uniform probability distribution over
all of its range. If you want all positive real numbers to be possible,
you must let there be some numbers $m$ and $n$ such that the
probability that your random number $x$ satisfies $m \leq x < m + 1$
is less than the probability that $n \leq x < n + 1$.
Since you want to be able to choose any positive real number,
and you don't seem to want any one number to be much more likely to be
chosen than any other number near it,
I'll consider only continuous distributions over the interval $[0,\infty)$.
A number selected from a continuous distribution can be any real number
in the range of the distribution, but for any particular number $k$
in that range, the probability that the random number will be exactly
equal to $k$ is zero.
(See this earlier question and its answers for further discussion of that fact.)
If you choose two numbers independently using identical continuous
probability distributions, it is not forbidden for the second number
to be equal to the first, but the probability of that event is zero.
So an argument by symmetry can show that the first number is greater
with probability exactly $\frac 12$, provided you have first defined
an actual continuous probability distribution over the positive real numbers
(and have accepted the necessary fact that this distribution
will be non-uniform).
There is also a way to do this by use of the $x,y$ plane.
We let $x$ be chosen randomly according to a continuous distribution over
$[0,\infty)$, and also let $y$ be chosen independently according to
an identical distribution.
It is then possible to define a joint distribution function for $(x,y)$
over the $x,y$ plane such that the probability of the point $(x,y)$
falling in any particular region is the integral of the joint distribution function over that region.
So define a suitable probability distribution, find the joint distribution,
integrated it over the (infinite) region of the $x,y$ plane where
$x < y$ and $y > 0$, and show that this integral equals $\frac 12.$
(The easiest way to show this may again be by a symmetry argument.)


text:
\begin{document}

\title{Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization

}

\titlerunning{Sparse Perturbations for Improved Convergence in SZO Optimization}

\author{Mayumi Ohta\inst{1}\and
Nathaniel Berger\inst{1} \and
Artem Sokolov\inst{1}\and
Stefan Riezler\inst{1,2}}

\authorrunning{M. Ohta et al.}

\institute{Department of Computational Linguistics \and Interdisciplinary Center for Scientific Computing (IWR)\\
Heidelberg University\\
Im Neuenheimer Feld 325\\
69120 Heidelberg, Germany \\
\email{\{ohta,berger,sokolov,riezler\}@cl.uni-heidelberg.de}\\
\url{https://www.cl.uni-heidelberg.de/statnlpgroup/}}

\maketitle

\begin{abstract}
Interest in stochastic zeroth-order (SZO) methods has recently been revived in black-box optimization scenarios such as adversarial black-box attacks to deep neural networks. SZO methods only require the ability to evaluate the objective function at random input points, however, their weakness is the dependency of their convergence speed on the dimensionality of the function to be evaluated. We present a sparse SZO optimization method that reduces this factor to the expected dimensionality of the random perturbation during learning. We give a proof that justifies this reduction for sparse SZO optimization for non-convex functions. Furthermore, we present experimental results for neural networks on MNIST and CIFAR that show empirical sparsity of true gradients, and faster convergence in training loss and test accuracy and a smaller distance of the gradient approximation to the true gradient in sparse SZO compared to dense SZO.

\keywords{Nonconvex Optimization \and Gradient-free Optimization \and Zeroth-order Optimization.}
\end{abstract}

\section{Introduction}

Zeroth-order optimization methods have gained renewed interest for solving machine learning problems where only the zeroth-order oracle, i.e., the value of the objective function but no explicit gradient, is available. Recent examples include black-box attacks on deep neural networks where adversarial images that lead to misclassification are found by approximating the gradient through a comparison of function values at random perturbations of input images \cite{ChenETAL:17}. The advantage of simple random search for scalable and reproducible gradient-free optimization has also been recognized in reinforcement learning \cite{ManiaETAL:18,SalimansETAL:17} and hyperparameter tuning for deep neural networks \cite{EbrahimiETAL:17}, and it is a mainstay in optimization of black-box systems and in simulation optimization \cite{Fu:06,NesterovSpokoiny:15}.
While zeroth-order optimization applies in principle even to non-differentiable functions, in practice Lipschitz-smoothness of the black-box function being evaluated can be assumed. This allows to prove convergence for various zeroth-order gradient approximations \cite{AgarwalETAL:10,DuchiETAL:15,FlaxmanETAL:05,GhadimiLan:12,NesterovSpokoiny:15,Shamir:17,YueJoachims:09}. However, even in the optimal case, zeroth-order optimization of $n$-dimensional functions suffers a factor of $\sqrt{n}$ in convergence rate compared to first-order gradient-based optimization.
The goal of our paper is to show theoretically and practically that \emph{sparse perturbations} in stochastic zeroth-order (SZO) optimization can improve convergence speed considerably by replacing the dependency on the dimensionality of the objective function by a dependency on the expected dimensionality of the random perturbation vector. This approach can be motivated by an observation of empirical sparsity of gradients in our experiments on neural networks, or by natural sparsity of gradients in applications to linear models with sparse input features \cite{SokolovETAL:18}.
We give a general convergence proof for non-convex stochastic zeroth-order optimization for Lipschitz-smooth functions that is independent of the dimensionality reduction schedule applied, and shows possible linear improvements in iteration complexity. Our proof is based on \cite{NesterovSpokoiny:15} and fills in the necessary gaps to verify the dependency of convergence speed on the dimensionality of the perturbation instead of on the full functional dimensionality.
We present experiments that perform dimensionality reduction on the random perturbation vector by iteratively selecting parameters with high magnitude for further SZO tuning, and freezing other parameters at their current values. Another dimensionality reduction technique selects random masks by the heldout performance of selected sub-networks, and once a sub-network architecture is identified, it is further fine-tuned by SZO optimization.
In our experiments, we purposely choose an application that allows optimization with standard first-order gradient-based techniques, in order to show improved gradient approximation by our sparse SZO technique compared to standard SZO with full perturbations. Our experimental results confirm a smaller distance to the true sparse gradient for the gradient obtained by sparse SZO, and improved convergence in training loss and test accuracy.
Furthermore, we compare our technique to a zeroth-order version of iterative magnitude pruning \cite{FrankleCarbin:19,HanETAL:15}. This technique zeros-out unimportant parts of the weight vector while our proposed technique zeros-out only perturbations and freezes unimportant parts of the weight vector at their current values. We find similar convergence speed, but a strong overtraining effect on the test set if weights are pruned to zero values. An estimation of the local Lipschitz constant for the trained models shows that it is growing in the number of iterations for the pruning approach, indicating that zeroing-out low magnitude weights may lead the optimization procedure in a less smooth region of the search space. We conjecture that a search path with a small local Lipschitz constant might have a similar desirable effect as flat minima \cite{KeskarETAL:17} in terms of generalization on unseen test data. Our code is publicly available\footnote{\UrlFont{https://github.com/StatNLP/sparse\_szo}}.

\section{Related Work}

SZO techniques in optimization date back to the finite-difference method for gradient estimation of \cite{KieferWolfowitz:52} where the value of each component of a weight vector is perturbed separately while holding the other components at nominal value. This technique has since been replaced by more efficient methods based on simultaneous perturbation of all weight vector components \cite{KushnerYin:03,Spall:92,Spall:03}. The central idea of these approaches can be described as approximating non-differentiable functions by smoothing techniques, and applying first-order optimization to the smoothed function \cite{FlaxmanETAL:05}. Several works have investigated different update rules and shown the advantages of two-point or multi-point feedback for improved convergence speed \cite{AgarwalETAL:10,DuchiETAL:15,GhadimiLan:12,LiuETAL:18,NesterovSpokoiny:15,Shamir:17,YueJoachims:09}. Recent works have investigated sparsity methods for improved convergence in high dimensions \cite{BalasubramanianGhadimi:18,WangETAL:18}. These works have to make strong assumptions of function sparsity or gradient sparsity. A precursor to our work that applies sparse SZO to linear models has been presented by \cite{SokolovETAL:18}.

Connections of SZO methods to evolutionary algorithms and reinforcement learning have first been described in \cite{Spall:03}. Recent work has applied SZO techniques successfully to reinforcement learning and hyperparameter search for deep neural networks \cite{EbrahimiETAL:17,ManiaETAL:18,PlappertETAL:18,SalimansETAL:17,SehnkeETAL:10}. Similar to these works, in our experiments we apply SZO techniques to Lipschitz-smooth deep neural networks.

Recent practical applications of SZO techniques have been presented in the context of adversarial black-box attacks on deep neural networks. Here a classification function is evaluated at random perturbations of input images with the goal of efficiently finding images that lead to misclassification  \cite{ChenETAL:17,ChengETAL:19}. Because of the high dimensionality of the adversarial attack space in image classification, heuristic methods to dimensionality reduction of perturbations in SZO optimization have already put to practice in \cite{ChenETAL:17}. Our approach presents a theoretical foundation for these heuristics.

\section{Sparse Perturbations in SZO Optimization for Nonconvex Objectives}

We study a stochastic optimization problem of the form
\begin{align}
 \min_\w f(\w), \text{ where } f(\w) := \E_\x[F(\w, \x)],
\end{align}
and where $\E_\x$ denotes the expectation over inputs $\x \in \X$, and $\w \in \R^n$ parameterizes the objective function $F$.
We address the case of non-convex functions $F$ for which we assume Lipschitz-smoothness\footnote{$C^{p,k}$ denotes the class of $p$ times differentiable functions whose $k$-th derivative  is Lipschitz continuous.}, i.e.,
$F(\w,\x) \in C^{1,1} $ is Lipschitz-smooth $ \mathrm{iff} \; \forall \w, \w', \x:
  \norm{\nabla F(\w,\x) - \nabla F(\w',\x)} \leq L(F) \norm{\w - \w'}$,
where $\norm{\cdot}$ is the L2-norm and $L(F)$ denotes the Lipschitz constant of $F$. This condition is equivalent to
\begin{align}\label{def:lipschitz}
  \lvert F(\w') - F(\w) - \langle \nabla F(\w), \w' - \w\rangle\rvert \leq \frac{L(F)}{2} \norm{\w - \w'}^2.
\end{align}
It directly follows that $f\in C^{1,1}$ if $F\in C^{1,1}$.

\cite{NesterovSpokoiny:15} show how to achieve a smooth version of an arbitrary function $f(\w)$ by Gaussian blurring that assures continuous derivatives everywhere in its domain. In their work, random perturbation of parameters is based on sampling a $n$-dimensional Gaussian random vector $\ug$ from a zero-mean isotropic multivariate Gaussian with unit $n \times n$ covariance matrix $\Sigma = \bm{I}$. The probability density function $\p(\ug)$ is defined by
\begin{align}
  \mathbf{u} &\sim \N(\bm{0}, \Sigma),\\
  \p(\mathbf{u}) &:=\frac{1}{\sqrt{(2\pi)^n\cdot \det\Sigma}} e^{-\frac{1}{2}\mathbf{u}^\top\Sigma^{-1}\mathbf{u}}.
\end{align}

A Gaussian approximation of a function $f$ is then obtained by the expectation over perturbations $\E_{\ug}[f(\w + \mu \ug)]$, where $\mu > 0$ is a smoothing parameter.
Furthermore, a Lipschitz-continuous gradient can be derived even for a non-differentiable original function $f$ by applying standard differentiation rules to the Gaussian approximation, yielding $\E_{\ug}[\frac{f(\w + \mu \ug) - f(\w)}{\mu}\ug]$.

The central contribution of our work is to show how a sparsification of the random perturbation vector $\ug$ directly enters into improved bounds on iteration complexity. This is motivated by an observation of empirical sparsity of gradients in our experiments, as illustrated in the supplementary material (Figures \ref{fig:sparsity-cifar} and \ref{fig:sparsity-mnist}). Concrete techniques for sparsification will be discussed as parts of our algorithm (Section \ref{sec:algo}), however, our theoretical analysis applies to any method for sparse perturbation.
Let $\m^{(t)} \in \{0,1\}^{n}$ be a mask specified at iteration $t$, and let $\odot$ denote the componentwise multiplication operator. A sparsified version $\bar{\vb}^{(t)}$ of a vector $\vb^{(t)} \in \R^{n}$ is gotten by
\begin{align}
  \bar{\vb}^{(t)} := \m^{(t)} \odot \vb^{(t)}.
\end{align}
The number of nonzero parameters of $\bar{\vb}^{(t)}$ is defined for a given mask $\m^{(t)}$ as
$\bar{n}^{(t)} := \lVert \m^{(t)} \rVert.$
Given the definition of a sparsification mask stated above, we can define a sparsified Gaussian random vector drawn from $\N(\bm{0}, \bm{I})$ by $\ub := \m \odot \ug$. Using this notion of sparse perturbation, we redefine the smooth approximation of $f$, with smoothing parameter $\mu > 0$, as
\begin{align}
 f_\mu(\w) :=& \E_{\ub}\left[ f(\w+\mu\ub) \right] .
\end{align}
Note that $f_\mu$ is Lipschitz-smooth with $L(f_\mu) < L(f)$.

\section{Convergence Analysis for Sparse SZO Optimization}

\cite{NesterovSpokoiny:15} show that for Lipschitz-smooth functions $F$, the distance of the gradient approximation to the true gradient can be bounded by the Lipschitz constant and by the norm of the random perturbation. The term $\E_{\ug}[\norm{\ug}^p]$ can itself be bounded by a function of the exponent $p$ and the dimensionality $n$ of the function space. This is how the dependency on $n$ enters iteration complexity bounds and where an adaptation to sparse perturbations enter the picture. The simple case of the squared norm of the random perturbation given below illustrates the idea. For $p=2$, we have
\begin{align}
\E_{\ub}\left[\norm{\ub}^2\right] &= \E_{\ub}\left[\bar{u}_1^2+\bar{u}_2^2+\cdots+\bar{u}_n^2\right] \nonumber\\
&= \E_{\ub}\left[\bar{u}_1^2\right]+\E_{\ub}\left[\bar{u}_2^2\right]+\cdots+\E_{\ub}\left[\bar{u}_n^2\right] \nonumber\\
&= \V_{\ub}\left[\bar{u}_1\right]+\V_{\ub}\left[\bar{u}_2\right]+\cdots+\V_{\ub}\left[\bar{u}_n\right] \nonumber\\
&= \bar{n}. \label{eq:lemma1_p_2}
\end{align}
Intuitively this means that if a coordinate $i$ in the parameter space is not perturbed, no variance $\V_{\ub}[\bar{u}_i]$ is incurred. The smaller the variance, the smaller the factor $\bar{n}$ that directly influences iteration complexity bounds.
The central Lemma \ref{lemma1} gives a bound on the expected norm of the random perturbations for the general case of $p \geq 2$: Intuitively, if several coordinates are masked and thus not perturbed, the determinant of the covariance matrix reduces to a product of variances of the unmasked parameters. This allows us to bound the perturbation factor for each input by $\bar{n} \ll n$ where the sparsity pattern is given by the masking strategy determined in the algorithm (see Section~\ref{sec:algo}).
\begin{lemma}\label{lemma1}
Let $\ub = \m \odot \mathbf{u}$ with $\mathbf{u} \sim \N(\bm{0}, \bm{I})$, then
  \begin{align}
    \E_{\ub}\left[\norm{\ub}^p\right] \leq (\bar{n} + p)^{\sfrac{p}{2}} ~ \text{for} \; p \geq 2. \label{eq:lemma1}
    \end{align}
  \end{lemma}
Given the reduction of the perturbation factor to $\bar{n} \ll n$, we can use the reduced factor in further Lemmata and in the main Theorem that shows improved iteration complexity of sparse SZO optimization. In the following we will state the Lemmata and Theorems that extend \cite{NesterovSpokoiny:15} to the case of sparse perturbations. For completeness, full proofs of all Lemmata and Theorems can be found in the supplementary material.

Lemma \ref{lemma2} applies standard differentiation rules to the function $f_\mu(\w)$, yielding a Lipschitz-continuous gradient.

\begin{lemma}\label{lemma2}
Let $F\in C^{1,1}$ and $\ub = \m \odot \mathbf{u}$ with  $\mathbf{u} \sim \N(\bm{0}, \bm{I})$. Then we have
  \begin{align}
    \nabla f_\mu(\w) & = \E_{\ub}[\frac{f(\w + \mu \ub)}{\mu}\ub] \label{eq:1-point}\\
    & = \E_{\ub}[\frac{f(\w + \mu \ub) - f(\w)}{\mu}\ub] \label{eq:2-point}\\
    & = \E_{\ub}[\frac{f(\w + \mu \ub) - f(\w - \mu \ub)}{2\mu}\ub]. \label{eq:2-sided}
    \end{align}
  \end{lemma}

In the rest of this paper we define our update rule as
\begin{align}\label{def:g_mu}
g_\mu(\w) := \frac{f(\w+\mu\ub) - f(\w)}{\mu}\ub
\end{align}
from (\ref{eq:2-point}).
Lemma \ref{lemma2} implies that $g_\mu(\w)$ is an unbiased estimator of $\nabla f_\mu(\w)$.

The next Lemma shows how to bound the distance of the gradient approximation to the true gradient in terms of $\mu$, $L(f)$, and the number of perturbations~$\bar{n}$.

\begin{lemma}\label{lemma3}
Let $f\in C^{1,1}$ Lipschitz-smooth, then
  \begin{align}
    \lVert \nabla f(\w) \rVert^2 &\leq 2 \lVert \nabla f_\mu(\w) \rVert^2 + \frac{\mu^2L^2(f)}{2} (\bar{n}+4)^{3}. \label{eq:lemma3}
    \end{align}
  \end{lemma}

The central Theorem shows that the iteration complexity of an SZO algorithm based on update rule \eqref{def:g_mu} is bounded by the Lipschitz constant $L$ and the expected dimensionality $\hat{n}$ of sparse perturbations with respect to iterations:
\begin{theorem}\label{theorem1}
Assume a sequence $\{\w^{(t)}\}_{t\geq 0}$ be generated by Algorithm \ref{algorithm1}. Let $\mathcal{X} = \{\x^{(t)}\}_{t\geq 0}$ and $ \bar{\mathcal{U}} = \{\ub^{(t)}\}_{t\geq 0}$. Furthermore, let $f_\mu^\star$ denote a stationary point such that $f_\mu^\star \leq f_\mu(w^{(t)}) ~ \forall \; t>0$  and $\hat{n} \geq \E_{t}[\bar{n}^
{(t)}] := \frac{1}{T+1}\sum_{t=0}^{T+1}\bar{n}^
{(t)}$ the upper bound of the expected number of nonzero entries of~$\bar{\mathcal{U}}$. Then, choosing learning rate $\hat{h} = \frac{1}{4(\hat{n}+4)L}$ and $\mu = \Omega{\left(\dfrac{\epsilon}{\hat{n}^{\sfrac{3}{2}}L}\right)}$ where $L(f)\leq L$ for all $f(\w^{(t)})$, we have
  \begin{align}
    \E_{\bar{\mathcal{U}},\mathcal{X}}\left[\norm{\nabla f(\w^{(T)})}^2\right] \leq \epsilon^2
  \end{align}
for any $T = \bigO{\left(\frac{\hat{n}L}{\epsilon^2}\right)}$.
\end{theorem}

Note that $\hat{n} \geq \E_{t}\left[\bar{n}^{(t)}\right]$ is much smaller than $n = \E_{t}\left[n^{(t)}\right] = \frac{1}{T+1}\sum_{t=0}^{T+1} n$, if $\bar{n}^{(t)}$ is chosen such that $\bar{n}^{(t)} \ll n$ at each iteration $t>0$ of Algorithm \ref{algorithm1}. This Theorem implies that both strong sparsity patterns and the smoothness of the objective function can boost the convergence speed up to linear factor.

\begin{table}[t]
    \begin{center}
    \begin{tabular}{ccc}
        \toprule
         dataset & MNIST & CIFAR-10 \\
         \midrule
         trainset size & 50,000 & 40,000\\
         devset size & 10,000 & 10,000\\
         testset size & 10,000 & 10,000\\
         architecture & feed-forward NN & CNN\\
         model size & 266,610 & 4,301,642\\
         batch size & 64  & 64 \\
         learning rate $h$ & 0.2 & 0.1  \\
         smoothing $\mu$ & 0.05  & 0.05  \\
         variance & 1.0  & 1.0 \\
         total epochs & 100 & 100\\
         sparsification interval & 5 epochs & 5 epochs \\
         \bottomrule
    \end{tabular}
    \end{center}
    \caption{Data statistics and system settings.
    }
    \label{table:hyperparameters}
\end{table}

\section{Algorithms for Sparse SZO Optimization}
\label{sec:algo}

\begin{algorithm}[t!]
  \caption{Sparse SZO Optimization}\label{algorithm1}
  \begin{algorithmic}[1]
    \State INPUT: dataset $\X=\{\x_0, \cdots, \x_T\}$, sequence of learning rates $h$, sparsification interval $s$, number of samples $k$, smoothing parameter $\mu>0$
    \State Initialize mask: $\m^{(0)} = \bm{1}^n$ \hfill ($\bar{n}^{(0)} = n$)
    \label{line:init_mask}
    \State Initialize weights: $\w^{(0)}$
    \For{$t=0,\cdots, T$}
    \If{$\mathrm{mod}(t,s) = 0$}
      \State Update mask $\m^{(t')} = \mathrm{get\_mask}(\w^{(t)})$ \label{line:get_mask}
      \If{pruning}
      \State  $\w^{(t)} = \m^{(t')} \odot \w^{(t)}$\label{line:set_weights}
      \label{line:mask_weights}
      \EndIf
    \EndIf

    \State Observe $\x^{(t)} \in \X$
    \For{$j=1, \cdots, k$}

    \State Sample unit vector $\mathbf{u}^{(t)} \sim \N(\bm{0},\bm{I})$
    \State Apply mask $\ub^{(t)} = \m^{(t')} \odot \mathbf{u}^{(t)}$ \hfill ($\bar{n}^{(t)} \ll n$)
    \label{line:mask_perturbations}
    \State Compute $g_\mu^{(j)}(\w^{(t)})$
    \EndFor
    \State Average $g_\mu(\w^{(t)}) = \underset{j}{\mathrm{avg}}(g_\mu^{(j)}(\w^{(t)}))$
    \State Update $\w^{(t+1)} = \w^{(t)} - h^{(t)}g_\mu(\w^{(t)})$

    \EndFor
    \State OUTPUT: sequence of $\{\w^{(t)}\}_{t\geq 0}$
  \end{algorithmic}
\end{algorithm}

\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{img/szo-results-new-util_lipschitz_f-mu_f_numerator.pdf}
\caption{Distance of gradient approximation to true gradient on training set, interpolation factor $0.99$.}
\label{fig:gradnorm}
\end{figure*}

\subsection{Masking strategies}
Algorithm \ref{algorithm1} starts with standard SZO optimization with full perturbations in the first iteration. This is done by initializing the mask to a $n$-dimensional vector of coordinates with value $1$ (line \ref{line:init_mask}). Guided by a schedule that applies sparsification at every $s$-th iteration, the  function $\mathrm{get\_mask(\cdot)}$ is applied (line \ref{line:get_mask}). We implemented a first strategy called \emph{magnitude masking}, and another one called \emph{random masking}. In \emph{magnitude masking}, we sort the indices according to their L1-norm magnitude, set a cut-off point, and mask the weights below the threshold. In \emph{random masking}, we sample 50 random mask patterns and select the one that performs best according to accuracy on a heldout set. Following \cite{FrankleETAL:19}, the sparsification interval corresponds to reducing 20\% of the remaining unmasked parameters at every 5 epochs.

\begin{figure*}[t]
\centering

\includegraphics[width=\textwidth]{img/szo-results-new-train_cuml_reward_nce.pdf}
\caption{Cumulative values for cross-entropy loss of sparse and dense SZO algorithms on the training set.}
\label{fig:train_loss}
\end{figure*}

\begin{figure*}[t]
\centering

\includegraphics[width=\textwidth]{img/szo-results-new-test_acc.pdf}\\
\caption{Multi-class classification accuracy of sparse and dense SZO algorithms on test sets.}
\label{fig:test_acc}
\end{figure*}

\subsection{Sparse perturbations with pruning or freezing}
Algorithm \ref{algorithm1} is defined in a general form that allows \emph{pruning} and \emph{freezing} of masked parameters. In the \emph{pruning} variant, the same sparsification mask that is applied to the Gaussian perturbations (line \ref{line:mask_perturbations}) is also applied to the weight vector itself (line \ref{line:mask_weights}). That is, we keep the weight values from the previous iteration at the index whose mask value is one, and reset the weight values to zero at the index whose mask value is zero. This can be seen as a straightforward sparse-SZO extension of the iterative magnitude pruning method with rewinding to the value of the previous iteration as proposed by \cite{FrankleETAL:19}.  In the \emph{freezing} variant, we apply the sparsification mask only to the Gaussian perturbations (line \ref{line:mask_perturbations}), and inherit all the weight values from the previous iteration. That is, we keep the weight value unchanged at the index whose mask value is zero, and allow the value to be updated at the index whose mask value is one.

\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{img/szo-results-new-util_lipschitz_t-1_t.pdf}
\caption{Estimated local Lipschitz smoothness $L_{\mathrm{local}}$ of sparse and dense SZO algorithms along search path, interpolation factor $0.99$.}
\label{fig:lipschitz}
\end{figure*}

\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{img/szo-results-new-util_lipschitz_t-1_t_numerator.pdf}\\
\includegraphics[width=\textwidth]{img/szo-results-new-util_lipschitz_t-1_t_denominator.pdf}\\
\caption{Denominator and numerator of estimated local Lipschitz smoothness $L_{\mathrm{local}}$ along search path, interpolation factor $0.99$.}
\label{fig:lipschitz-denominator-numerator}
\end{figure*}

\section{Experiments}

We purposely chose experimental tasks where the true gradient can be calculated exactly in order to experimentally verify the improved gradient approximation by sparse perturbations in SZO. While the convergence rate in SZO is always is suboptimal compared to first-order optimization due to the used gradient approximation (see \cite{DuchiETAL:15} or \cite{Shamir:17}), our proofs show that sparse perturbations improve the distance of the approximate gradient to the true gradient (Lemma \ref{lemma3}) and thus the convergence rate (Theorem \ref{theorem1}). The experimental results given in the following confirm our theoretical analysis.

\subsection{Task and datasets}
We apply our sparse SZO algorithm to standard image classification benchmarks on the MNIST \cite{LeCun:98} and CIFAR-10 \cite{Krizhevsky:09} datasets. Since the SZO optimizers are less common in an off-the-shelf API package bundled in a framework, we implemented our custom SZO optimizers utilizing \texttt{pytorch}, and the data was downloaded via torchvision package v0.4.2. We followed the pre-defined train-test split, and partitioned 20\% of the train set for validation.
Model performance is measured by successive evaluation of the gradient norm on the training set, multi-class classification accuracy on the test set, cumulative cross-entropy loss on the training set, and the local function smoothness, estimated by the local Lipschitz constant computed as
\begin{align}
L_{\mathrm{local}} := \frac{\norm{\nabla f(\w^{(t-1)}) - \nabla f(\w^{(t)})}}{\norm{\w^{(t-1)} - \w^{(t)}}}.
\label{local_lipschitz}
\end{align}

\subsection{Architectures and experimental settings}
For the MNIST experiments, we constructed a fully-connected feed-forward neural network models with 3 layers including batch normalization \cite{Ioffe:15} after each layer. For the CIFAR-10 experiments, we built a convolutional neural network with 2 convolutional layers with kernel size 3 and stride 1. After taking max pooling of these two convolutional layers, we use 2 extra fully-connected linear layers on top of it. We employed the xavier-normal weights initialization method \cite{Glorot:10} for all setups. Each model is trained by minimizing a standard cross-entropy loss for 100 epochs with batch size 64. We used a constant learning rate of 0.2 for MNIST and 0.1 for CIFAR, a constant smoothing parameter of 0.05, and two-sided perturbations in the SZO optimization for both datasets. We sampled 10 perturbations per update from a zero-centered Gaussian distribution with variance 1.0, computed the gradients for each, then the average was taken before update.
Applying the 20\% reduction schedule 20 times throughout the training, the active model parameters were reduced from 266,610 to 3,844 in MNIST experiments, from 4,301,642 to 61,996 in CIFAR experiments. We computed sparsity as $1-\frac{\bar{n}^{(t)}}{n^{(t)}}$ every time we update the mask pattern. The sparsity value along iteration is given in the upper x-axis of each plot. The lower $x$-axis shows the number of examples visited during training in thousands. If indicated, plotted curves are smoothed by linear interpolation with the previous values. All plots show mean and standard deviation of results for 3 training runs under different random seeds. A summary of data statistics and system settings can be found in Table \ref{table:hyperparameters}.

\subsection{Experimental results}
Our experimental task was purposely chosen as an application that allows optimization with standard first-order (SFO) gradient-based techniques for comparison with SZO methods.
Figure \ref{fig:gradnorm} shows that the distance of the approximate gradient to the true gradient converges to zero at the fastest rate for freezing methods, proving empirical support for \eqref{d1} in Lemma \ref{lemma3}. All four sparse SZO variants approach the true gradients considerably faster in most training steps on both training datasets than dense SZO (i.e.,  the full dimension of parameters is perturbed in each training step). We see that dense SZO is diverging from the true gradient on the CIFAR dataset where more than 4 million parameters are trained.

Figure \ref{fig:train_loss} gives cumulative values of the cross-entropy loss function on the respective training sets. We see that convergence in cross-entropy loss is similar for sparse and dense SZO variants on MNIST and advantageous for sparse SZO on CIFAR, with both weight pruning methods showing a slight divergence in cross-entropy loss.

Figure \ref{fig:test_acc} shows the accuracy of multi-class classification on MNIST and CIFAR-10 for the sparse and dense SZO variants. We see the fastest convergence in test accuracy for freezing methods, compared to pruning and dense SZO. Interestingly, we see that the test accuracy decreases after a while for all pruning variants, while it continues to increase for the freezing variants and the dense SZO algorithm.

\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{img/szo-results-new-test_neighbourhood_05.pdf}
\caption{Estimated local Lipschitz smoothness $L_{\mathrm{neighbor}}$ on test set in neighborhood of $w^{(t)}$, interpolation factor $0.8$.}
\label{fig:lipschitz-neighborhood}
\end{figure*}

One possibility to analyze this effect is to inspect the estimate of the local Lipschitz smoothness $L_{\mathrm{local}}$ defined in~\eqref{local_lipschitz} along the current search path on the training set. Figure~\ref{fig:lipschitz} shows that $L_{\mathrm{local}}$ decreases considerably along the search trajectory for sparse SZO optimization, with a faster decrease for freezing than for pruning methods. However, it increases considerably for the dense variant, leading the optimization procedure into less smooth areas of the search space. In order to verify that this is not a trivial effect due to pruned weight vectors, we consider numerator and denominator of $L_{\mathrm{local}}$ separately in Figure \ref{fig:lipschitz-denominator-numerator}. We see that the denominator and numerator are decreasing at different speeds for the sparse variants, with relatively larger differences between gradients causing an increase in the Lipschitz quotient. The numerator $\norm{\nabla f(w^{(t-1)}) - \nabla f(w^{(t)})}$ is successively reduced in the sparse methods, with a faster reduction for freezing than for pruning. The reduction indicates that sparse SZO methods find a path converging to the optimal point, while the dense variant seems not to be able to find such a path, but instead stays at the same distance or even increases the distance from the previous step.

Finally, we evaluate an estimate of the local Lipschitz smoothness in a neighborhood $\vb \sim \mathrm{Uniform}(-0.5,0.5)$ around the current parameter values $\w^{(t)}$ on the test set. $L_{\mathrm{neighbor}}$ is estimated by taking  the maximum of 10 samples per batch as
\begin{align}
L_{\mathrm{neighbor}} := \underset{\vb}{\max} \frac{\norm{\nabla f(\w^{(t)}) - \nabla f(\w^{(t)}+\vb)}}{\norm{\vb}}.
\label{local_lipschitz_neighbor}
\end{align}
Figure \ref{fig:lipschitz-neighborhood} shows that $L_{\mathrm{neighbor}}$ is staying roughly constant on the test set in the neighborhood of the parameter estimates obtained during training for freezing and dense SZO. However, it is increasing considerably for both variants of pruning, indicating that pruning methods converge to less smooth regions in parameter space.

\section{Conclusion}

SZO methods are flexible and simple tools for provably convergent optimization of black-box functions only from function evaluations at random points. A theoretical analysis of these methods can be given under mild assumptions of Lipschitz-smoothness of the function to be optimized. However, even in the best case, such gradient-free methods suffer a factor of $\sqrt{n}$ in iteration complexity, depending on the dimensionality $n$ of the evaluated function, compared to methods that employ gradient information. This makes SZO techniques always second-best if gradient information is available, especially in high dimensional optimization. However, SZO techniques may be the only option in black-box optimization scenarios where it is desirable as well to improve convergence speed. Our paper showed that the dimensionality factor can be reduced to the expected dimensionality of random perturbations during training, independent of the dimensionality reduction schedule employed. This allows considerable speedups in convergence of SZO optimization in high dimensions.
We presented experiments with masking schedules based on L1-magnitude and random masking, both confirming our theoretical result of an improved approximation of the true gradient by a sparse SZO gradient. This result is accompanied by an experimental finding of improved convergence in training loss and test accuracy.
A further experiment compared sparse SZO where masked parameters are frozen at their current values to a variant of sparse SZO where masked parameters are pruned to zero values. This technique can be seen as a sparse SZO variant of the well-known technique of iterative magnitude pruning \cite{FrankleCarbin:19,HanETAL:15}. Our results show that pruning techniques perform worse in the world of SZO optimization than fine-tuning unmasked parameters while freezing masked parameters. By further inspection of the local Lipschitz smoothness along the search path of different algorithms we find that pruning in the SZO world can lead the optimization procedure in a locally less smooth search area, while freezing seems to lead to a smoother search path even compared to dense SZO optimization.

\section*{Acknowledgements}
 We would like to thank Michael Hagmann for proofreading the theoretical analysis, and the anonymous reviewers for their useful comments. The research reported in this paper was supported in part by the German research foundation (DFG) under grant RI-2221/4-1.

\bibliographystyle{splncs04}
\bibliography{paper}

\newpage

\section*{Appendix}
\renewcommand{\thesubsection}{\Alph{subsection}}

\subsection{Notation}

In order to adapt the theoretical analysis of \cite{NesterovSpokoiny:15} to the case of sparse perturbations, the probability density function $\p_{\ub}(\ub)$ and expectations $\E_{\ub}[f(\ub)]$ of random variables with respect to it have to be carefully defined.
Given a sparsification mask $\m \in \{0,1\}^{n}$, let $I_{\mathrm{masked}} := \{i | m_i = 0\}$ be a set of indices whose mask value is zero. Likewise, let $I_{\mathrm{unmasked}} := \{i | m_i = 1\}$ be a set of indices whose mask value is one. The probability density function of random perturbations $\ug \sim \N(\bm{0}, \bm{I})$ can be expressed as a product of univariate probability density functions $\p(u_i)$, where $u_i \sim \N(0,1)$. Then the probability density function $\p_{\ub}(\ub)$ can be defined as a conditional probability density function $\p_{\ug|u_i = 0, i\in I_{\mathrm{masked}}}(\ug)$, conditioned on zero-valued entries $u_i = 0$ corresponding to masked indices $i\in I_{\mathrm{masked}}$. Since the number of nonzero parameters is determined by the sparsification mask as $|I_{\mathrm{unmasked}}| = \bar{n}$, we can reduce the product over the full dimensionality $i \in \{1, \cdots n\}$ to the product over unmasked entries $i \in I_{\mathrm{unmasked}}$. The conditional probability density function $\p_{\ug|u_i = 0, i\in I_{\mathrm{masked}}}(\ug)$ is then defined as
\begin{align}
\p_{\ug|u_i = 0, i\in I_{\mathrm{masked}}}(\ug) & = \prod_{i\in I_{\mathrm{unmasked}}} \p(u_i) \\
& = \left(\frac{1}{\sqrt{2\pi}}\right)^{\bar{n}} \prod_{i\in I_{\mathrm{unmasked}}} e^{-\frac{1}{2}u_i^2}.
\end{align}
The expectation with respect to $\ub$ is defined as conditional expectation using aforementioned conditional probability density function. Let $f: \R^n \rightarrow \R$ be an arbitrary function, let $\int_{\ug\upharpoonright} \cdot d\ug$ denote the integral $\int_{\ug|u_i=0, i\in I_{\mathrm{masked}}} \cdot d\ug$, and let $\p_{\ug\upharpoonright}$ denote the conditional probability density function $\p_{\ug|u_i = 0, i\in I_{\mathrm{masked}}}$, and let $\kappa := \sqrt{(2\pi)^{\bar{n}}}$. Then we have
\begin{align}
\E_{\ub}[f(\ub)] &:= \E_{\ug|u_i=0, i\in I_{\mathrm{masked}}}[f(\ug)] \\
&= \int_{\ug\upharpoonright}  ~f(\ug)\cdot \p_{\ug\upharpoonright}(\ug) d\ug\\

&= \frac{1}{\kappa} \int_{\ug\upharpoonright} ~f(\ug)\cdot \pdf d\ug.

\end{align}

In the following, we use the notation $\int_{\ug\upharpoonright} \cdot d\ug$ for $\int_{\ug|u_i=0, i\in I_{\mathrm{masked}}} \cdot d\ug$, and $\p_{\ug\upharpoonright}$ for $\p_{\ug|u_i = 0, i\in I_{\mathrm{masked}}}$.

\subsection{Proof for Lemma \ref{lemma1}}
\begin{proof}
Define by $\ut \in \R^{\bar{n}}$ a reduced vector that removes all zero entries from $\ub\in \R^n$. Taking an expectation over $\ub \in \R^n$ results in the same value as taking an expectation over $\ut \in \R^n$. This can be seen as follows:
\begin{align*}
\E_{\ub}\left[\norm{\ub}^p\right] &= \frac{1}{\kappa}\int_{\ug|u_i=0, i\in I_{\mathrm{masked}}}\norm{\ug}^p e^{-\frac{1}{2}\ug^\top \Sigma\ug} d\ug\\
&= \frac{1}{\kappa}\int_{\ug|u_i=0, i\in I_{\mathrm{masked}}} \left(\sum_{j=1}^{n} \lvert u_j \rvert^p \right) e^{-\frac{1}{2}\ug^\top \Sigma\ug} d\ug\\
&= \frac{1}{\kappa}\sum_{i\in I_{\mathrm{unmasked}}}\left(\int_{u_i} \lvert u_i \rvert^p  e^{-\frac{1}{2}u_i^2} d u_i \right)\\
&= \frac{1}{\kappa}\int_{\ut} \left(\sum_{i=1}^{\bar{n}} \lvert u_i \rvert^p \right) e^{-\frac{1}{2}\ut^\top \tilde{\Sigma}\ut} d\ut\\
&= \frac{1}{\kappa} \int_{\ut}\norm{\ut}^p e^{-\frac{1}{2}\ut^\top \tilde{\Sigma}\ut} d\ut\\
&= \E_{\ut}\left[\norm{\ut}^p\right]
\end{align*}
where $\tilde{\Sigma}$ is a $\bar{n} \times \bar{n}$ unit covariance matrix with $\tilde{\Sigma}=\bm{I}$.

Let $p \geq 2$ and $\tau \in (0,1)$. Recalling that $\ub \in \R^{n}$, $\ut \in \R^{\bar{n}}$, and $\tilde{\Sigma}\in \R^{\bar{n}\times \bar{n}}$, we have
\begin{align}
\E_{\ub}\left[\norm{\ub}^p\right] &= \E_{\ut}\left[\norm{\ut}^p\right] \nonumber\\
&=\frac{1}{\sqrt{(2\pi)^{\bar{n}}}} \int_{\ut}\norm{\ut}^p e^{-\frac{\tau + (1-\tau)}{2} \ut^\top \ut} d\ut \nonumber\\
&= \frac{1}{\sqrt{(2\pi)^{\bar{n}}}} \int_{\ut}\norm{\ut}^p e^{-\frac{\tau}{2} \ut^\top \ut}e^{-\frac{1-\tau}{2} \ut^\top \ut} d\ut \nonumber\\
&\leq \frac{1}{\sqrt{(2\pi)^{\bar{n}}}} \int_{\ut} \left(\frac{p}{\tau e}\right)^{\frac{p}{2}} e^{-\frac{1-\tau}{2} \ut^\top \ut} d\ut \label{e1}\\
&= \left(\frac{p}{\tau e}\right)^{\frac{p}{2}} \frac{1}{\sqrt{(2\pi)^{\bar{n}}}}\int_{\ut} e^{-\frac{1}{2} \ut^\top\left(\frac{\tilde{\Sigma}}{1-\tau}\right)^{-1} \ut} d\ut \nonumber\\
&= \left(\frac{p}{\tau e}\right)^{\frac{p}{2}} \frac{1}{\sqrt{(2\pi)^{\bar{n}}}} \sqrt{(2\pi)^{\bar{n}} \cdot \det\left(\frac{\bar{\Sigma}}{1-\tau}\right)}\label{e5}\\
&= \left(\frac{p}{\tau e}\right)^{\frac{p}{2}} (1-\tau)^{-\frac{\bar n}{2}}\label{e2}\\
&\leq \left(\bar{n} + p\right)^{\frac{p}{2}} \label{e3}.
\end{align}
The first inequality \eqref{e1} follows from $t^p e^{-\frac{\tau}{2}t^2} \leq \left(\frac{p}{\tau e}\right)^\frac{p}{2}$ for $ t> 0$. The second inequality \eqref{e3} follows by minimizing $\left(\frac{p}{\tau e}\right)^{\frac{p}{2}} (1-\tau)^{-\frac{n}{2}}$ in $\tau \in (0,1)$.
Full proofs of these inequalities are given in subsection \ref{misc}.
\end{proof}

\subsection{Proof for Lemma \ref{lemma2}}\label{proof:lemma2}
\begin{proof}

\begin{align}
\nabla_\w f_{\mu}(\w) &= \nabla_\w \E_{\ub}\left[f(\w + \mu\ub)\right] \nonumber\\
&= \nabla_\w \int_{\ug\upharpoonright} \p_{\ug\upharpoonright}(\ug)~ f(\w + \mu\ug) ~d\ug \nonumber\\
&= \int_{\ug\upharpoonright} \nabla_\w ~\p_{\ug\upharpoonright}(\ug)~ f(\w + \mu\ug) ~d\ug \label{interchange}\\
&= \frac{1}{\kappa}\int_{\ug\upharpoonright} \nabla_\w ~ \pdf f(\w + \mu\ug) ~d\ug \nonumber\\
&= \frac{1}{\kappa}\int_{\y\upharpoonright} \nabla_\w ~ e^{-\frac{1}{2}\lVert\frac{\y - \w}{\mu}\rVert^2} f(\y) \frac{1}{\mu^n}~ d\y  \label{substitute_y}\\
&= \frac{1}{\kappa}\int_{\y\upharpoonright} \frac{\y - \w}{\mu^2 } e^{-\frac{1}{2\mu^2}\lVert\y - \w\rVert^2} f(\y) \frac{1}{\mu^n}~ d\y \nonumber\\
&= \frac{1}{\kappa}\int_{\ug\upharpoonright} \frac{\ug}{\mu} e^{-\frac{1}{2}\lVert\ug\rVert^2} f(\w + \mu\ug) ~d\ug \label{substitute_u}\\
&= \E_{\ub}\left[\frac{f(\w + \mu\ub)}{\mu} \ub \right] \nonumber
\end{align}

Since $f\in C^{1,1}$, we can interchange $\nabla$ and the integral in \eqref{interchange}. Furthermore, we substituted $\y = \w + \mu\ug$ in \eqref{substitute_y} and put it back in \eqref{substitute_u}.

Now, we show \eqref{eq:2-point} $\Leftrightarrow$ \eqref{eq:1-point}.
\begin{align}
&\E_{\ub}\left[\frac{f(\w + \mu\ub) - f(\w)}{\mu} \ub \right] \\
&= \frac{1}{\kappa}\int_{\ug\upharpoonright} \frac{f(\w + \mu\ug) - f(\w)}{\mu} \ug ~  \pdf d\ug \nonumber\\
&= \frac{1}{\kappa}\int_{\ug\upharpoonright} \frac{f(\w + \mu\ug)}{\mu} \ug ~  \pdf d\ug  - \frac{f(\w)}{\mu\kappa} \underset{=0}{\underbrace{ \int_{\ug\upharpoonright} \ug ~  \pdf d\ug}} \nonumber\\
&= \E_{\ub}\left[\frac{f(\w + \mu\ub)}{\mu} \ub \right] \label{eq:two-point1}
\end{align}

Lastly, we show \eqref{eq:2-sided} $\Leftrightarrow$ \eqref{eq:1-point}.
The expectation doesn't change even if we shift $\w$ by $\mu\ub$, hence
\begin{align}
\E_{\ub}\left[\frac{f(\w) - f(\w - \mu\ub)}{\mu} \ub \right] &= \E_{\ub}\left[\frac{f(\w + \mu\ub) - f(\w)}{\mu} \ub \right] \\
&\overset{\eqref{eq:two-point1}}{=} \E_{\ub}\left[\frac{f(\w + \mu\ub)}{\mu} \ub \right].\label{eq:two-point2}
\end{align}
\begin{align*}
&\E_{\ub}\left[\frac{f(\w + \mu\ub) - f(\w - \mu\ub)}{2\mu} \ub \right]\\
&= \frac{1}{2} \left(\E_{\ub}\left[\frac{f(\w + \mu\ub)}{\mu} \ub \underset{=0}{\underbrace{- \frac{f(\w)}{\mu} \ub + \frac{f(\w)}{\mu}}} \ub - \frac{f(\w - \mu\ub)}{\mu} \ub \right]\right)\\
&= \frac{1}{2} \left(\E_{\ub}\left[\frac{f(\w + \mu\ub) - f(\w)}{\mu} \ub \right]  + \E_{\ub}\left[\frac{f(\w) - f(\w - \mu\ub)}{\mu} \ub \right]\right)\\
&\overset{\eqref{eq:two-point2}}{=} \frac{1}{2} \left(\E_{\ub}\left[\frac{f(\w + \mu\ub)}{\mu} \ub \right]  + \E_{\ub}\left[\frac{f(\w + \mu\ub)}{\mu} \ub \right]\right)\\
&= \E_{\ub}\left[\frac{f(\w + \mu\ub)}{\mu} \ub \right]
\end{align*}
\end{proof}

\subsection{Proof for Lemma \ref{lemma3}}
\begin{proof}
\begin{align}
&\norm{\nabla f_\mu(\w) - \nabla f(\w)} \\
&= \left\lVert\frac{1}{\kappa} \int_{\ug\upharpoonright} \left(\frac{f(\w+\mu\ug) - f(\w)}{\mu} - \langle \nabla f(\w),\ug \rangle \right) ~ \ug ~ e^{-\frac{1}{2}\lVert\ug\rVert^2} d\ug \right\rVert\label{d1}\\
&\leq \frac{1}{\kappa\mu}\int_{\ug\upharpoonright} \lvert f(\w+\mu\ug) - f(\w) - \mu\langle \nabla f(\w),\ug \rangle \rvert \norm{\ug} ~ e^{-\frac{1}{2}\lVert\ug\rVert^2} d\ug\label{d2}\\
&\overset{\eqref{def:lipschitz}}{\leq} \frac{\mu L(f)}{2\kappa} \int_{\ug\upharpoonright} \norm{\ug}^3 ~ e^{-\frac{1}{2}\lVert\ug\rVert^2} d\ug \nonumber\\
&= \frac{\mu L(f)}{2} \E_{\ub}\left[\norm{\ub}^3\right] \nonumber\\
&\overset{\eqref{eq:lemma1}}{\leq}\frac{\mu L(f)}{2} (\bar{n} + 3)^{\sfrac{3}{2}} \label{d3}
\end{align}

In the first equality \eqref{d1}, we used $\nabla f(\w) \overset{\eqref{eq:misc3}}{=}\E_{\ub}\left[ \langle \nabla f(\w),\ub \rangle \ub  \right] $\\
$= \frac{1}{\kappa}\int_{\ug\upharpoonright} \langle \nabla f(\w),\ug \rangle \ug ~ e^{-\frac{1}{2}\lVert\ug\rVert^2} d\ug$ (see Lemma \ref{misc3}). The first inequality \eqref{d2} follows because $\left\lVert\int f(x)dx \right\rVert \leq \int \left\lVert f(x) \right\rVert dx$ (the triangle inequality for integrals).

Setting $\ab \leftarrow \nabla f(\w)$ and $\bb \leftarrow \nabla f_\mu(\w)$ in Lemma \ref{lemma0}, we get
\begin{align*}
\norm{\nabla f(\w)}^2 &\overset{\eqref{eq:lemma0}}{\leq} 2\norm{\nabla f(\w) - \nabla f_\mu(\w)}^2 + 2\norm{\nabla f_\mu(\w)}^2\\
&\overset{\eqref{d3}}{\leq} \frac{\mu^2 L^2(f)}{2} (\bar{n} + 3)^3 + 2\norm{\nabla f_\mu(\w)}^2\\
&\leq \frac{\mu^2 L^2(f)}{2} (\bar{n} + 4)^3 + 2\norm{\nabla f_\mu(\w)}^2
\end{align*}
\end{proof}

\subsection{Proof for Theorem \ref{theorem1}}
\begin{proof}

\begin{align}
f_\mu(\w) - f(\w) &= \E_{\ub}\left[f(\w + \mu\ub)\right] - f(\w)\nonumber\\
&= \E_{\ub}\left[f(\w + \mu\ub) - f(\w) -\mu\langle \nabla f(\w), \ub\rangle\right]\label{c1}\\
&= \frac{1}{\kappa}\int_{\ug\upharpoonright}\left[f(\w + \mu\ug) - f(\w) -\mu\langle \nabla f(\w), \ug\rangle\right] \pdf d\ug\nonumber\\
&\overset{\eqref{def:lipschitz}}{\leq} \frac{1}{\kappa} \int_{\ug\upharpoonright} \frac{\mu^2 L(f)}{2}\norm{\ug}^2 \pdf d\ug\nonumber\\
&= \frac{\mu^2L(f)}{2}\E_{\ub}\left[\norm{\ub}^2\right] \nonumber\\
&\overset{\eqref{eq:lemma1_p_2}}{\leq} \frac{\mu^2 L(f)}{2}\bar{n}\label{a0}
\end{align}
The second equality \eqref{c1} follows because $\E_{\ub}\left[\ub\right] = \bm{0}$. Moreover, \eqref{a0} doesn't change even if we shift $\w$ by $\mu\ub$, therefore we have
\begin{align}
&\left[(f_\mu(\w) - f(\w)) - (f_\mu(\w + \mu\ug) - f(\w + \mu\ug))\right]^2\\ &\overset{\eqref{eq:misc}}{\leq} 2\left[f_\mu(\w) - f(\w)\right]^2 + 2\left[f_\mu(\w + \mu\ug) - f(\w + \mu\ug)\right]^2 \nonumber\\
&\overset{\eqref{a0}}{\leq} \frac{\mu^4 L^2(f)}{2}\bar{n}^2 + \frac{\mu^4 L^2(f)}{2}\bar{n}^2 \nonumber\\
&= \mu^4 L^2(f)\bar{n}^2\label{a1}
\end{align}

Setting $\ab \leftarrow f_\mu(\w + \mu\ug) - f_\mu(\w)$ and $\bb \leftarrow \mu \langle \nabla f_\mu(\w), \ug \rangle$ in Lemma \ref{lemma0}, we get
\begin{align}
&\left[f_\mu(\w + \mu\ug) - f_\mu(\w)\right]^2\\
&\overset{\eqref{eq:lemma0}}{\leq} 2\left[f_\mu(\w + \mu\ug) - f_\mu(\w) - \mu \langle \nabla f_\mu(\w), \ug \rangle\right]^2 + 2\left[\mu \langle \nabla f_\mu(\w), \ug \rangle\right]^2\nonumber\\
&\overset{\eqref{def:lipschitz}}{\leq} \frac{\mu^4 L^2(f_\mu)}{2}\norm{\ug}^4 + 2\mu^2 \langle \nabla f_\mu(\w), \ug \rangle ^2 \nonumber\\
&\leq \frac{\mu^4 L^2(f)}{2}\norm{\ug}^4 + 2\mu^2 \norm{\nabla f_\mu(\w)}^2\norm{\ug}^2\label{a2}
\end{align}
The last inequality follows because $L(f_\mu)<L(f)$ and the Cauchy-Schwarz inequality $\langle \ab, \bb \rangle^2 \leq \norm{\ab}^2 \norm{\bb}^2$.

Again, setting $\ab \leftarrow f(\w + \mu\w) - f(\w)$ and $\bb \leftarrow f_\mu(\w + \mu\w) - f_\mu(\w)$ in Lemma \ref{lemma0}, we obtain
\begin{align}
&\left[f(\w + \mu\ug) - f(\w)\right]^2\\
&\overset{\eqref{eq:lemma0}}{\leq} 2\left[(f_\mu(\w) - f(\w)) - (f_\mu(\w + \mu\ug) - f(\w + \mu\ug))\right]^2 + 22\left[f_\mu(\w + \mu\ug) - f_\mu(\w)\right]^2 \nonumber\\
&\overset{\eqref{a1},\eqref{a2}}{\leq} 2\mu^4 L^2(f)\bar{n}^2 + \mu^{4} L^2(f)\norm{\ug}^4 + 4\mu^2 \norm{\nabla f_\mu(\w)}^2\norm{\ug}^2 \label{a3}
\end{align}

Now, we evaluate the expectation of $\norm{g_\mu(\w)}^2$ wrt. $\x$ and $\ub$.
\begin{align}
\E_{\ub, \x}\left[\norm{g_\mu(\w)}^2\right] &\overset{\eqref{def:g_mu}}{=} \E_{\ub}\left[\left\lVert\frac{f(\w+\mu\ub) - f(\w)}{\mu}\ub\right\rVert^2\right] \nonumber\\
&= \E_{\ub}\left[\frac{1}{\mu^2}\left[ f(\w+\mu\ub) - f(\w)\right]^2 \cdot \norm{\ub}^2\right] \\
&\overset{(\ref{a3})}{\leq} \E_{\ub}\left[2\mu^{2} L^2(f)\bar{n}^2\norm{\ub}^2 + \mu^{2} L^2(f)\norm{\ub}^6 + 4\norm{\nabla f_\mu(\w)}^2 \norm{\ub}^4\right] \nonumber\\
&\overset{\eqref{eq:lemma1}}{\leq} 2\mu^2 L^2(f)\bar{n}^3 + \mu^2 L^2(f)(\bar{n}+6)^3 + 4(\bar{n}+4)^2\norm{\nabla f_\mu(\w)}^2 \nonumber\\
&\leq 3\mu^2 L^2(f)(\bar{n}+4)^3 + 4(\bar{n}+4)^2\norm{\nabla f_\mu(\w)}^2 \label{eq:lemma4}
\end{align}
The last inequality follows because $2\bar{n}^3 + (\bar{n} + 6)^3 \leq 3(\bar{n}+4)^3$.

From the Lipschitz-smoothness assumption \eqref{def:lipschitz} of $f_\mu$, we have
\begin{align}
f_\mu(\w^{(t+1)}) &\overset{\eqref{def:lipschitz}}{\leq} f_\mu(\w^{(t)}) + \langle \nabla f_\mu(\w^{(t)}), \w^{(t+1)}-\w^{(t)} \rangle + \frac{L(f_\mu)}{2}\norm{\w^{(t)} - \w^{(t+1)}}^2 \nonumber\\
&= f_\mu(\w^{(t)}) - h^{(t)}\langle \nabla f_\mu(\w^{(t)}), g_\mu(\w^{(t)}) \rangle + \frac{ (h^{(t)})^2 L(f_\mu)}{2}\norm{g_\mu(\w^{(t)})}^2 \label{a4}
\end{align}
In \eqref{a4}, we used the update rule $\w^{(t+1)} = \w^{(t)} - h^{(t)} g_\mu(\w^{(t)})$.
Taking the expectation wrt. $\x^{(t)}$ and $\ub^{(t)}$, we have
\begin{align*}
&\E_{\ub, \x}\left[f_\mu(\w^{(t+1)})\right]\\
&\leq \E_{\ub, \x}\left[f_\mu(\w^{(t)}) \right] - h^{(t)}\E_{\ub, \x}\left[\norm{\nabla f_\mu(\w^{(t)})}^2\right] + \frac{ (h^{(t)})^2 L(f_\mu)}{2}\E_{\ub, \x}\left[\norm{g_\mu(\w^{(t)})}^2 \right]\\
&\overset{\eqref{eq:lemma4}}{\leq} \E_{\ub, \x}\left[f_\mu(\w^{(t)}) \right] - h^{(t)}\E_{\ub, \x}\left[\norm{\nabla f_\mu(\w^{(t)})}^2\right] \nonumber\\
&\hspace{2em}+ \frac{(h^{(t)})^2 L(f)}{2}\left(4(\bar{n}^{(t)}+4) \E_{\ub, \x}\left[\norm{\nabla f_\mu(\w^{(t)})}^2\right] + 3\mu^2 L^2(f)(\bar{n}^{(t)}+4)^3 \right)
\end{align*}

Choosing $h^{(t)} = \frac{1}{4(\bar{n}^{(t)}+4)L(f)}$, we have
\begin{align}
\E_{\ub, \x}\left[f_\mu(\w^{(t+1)})\right]
&\leq \E_{\ub, \x}\left[f_\mu(\w^{(t)}) \right] - \frac{1}{8(\bar{n}^{(t)}+4)L(f)}\E_{\ub, \x}\left[\norm{\nabla f_\mu(\w^{(t)})}^2\right]\\
&\hspace{10em}+ \frac{3\mu^2}{32}L(f)(\bar{n}^{(t)}+4) \label{b1}
\end{align}

Recursively applying the inequalities above moving the index from $T+1$ to $0$, rearranging the terms and noting that $f_\mu^\star \leq f_\mu(w^{(t)})$ and $\hat{h} = \frac{1}{4(\hat{n}+4)L}$ where $L(f)\leq L$ for all $f(\w^{(t)})$ results in
\begin{align}
\E_{\bar{\mathcal{U}}, \X}\left[\norm{\nabla f_\mu(\w^{(T)})}^2\right] &\leq 8(\hat{n}+4)L\left[\frac{f_\mu(\w^{(0)})- f_\mu^\star}{T+1} + \frac{3\mu^2}{32}L(\hat{n}+4)\right]\label{b2}
\end{align}
Thus, we obtain
\begin{align}
\E_{\bar{\mathcal{U}}, \X}\left[\norm{\nabla f(\w^{(T)})}^2\right] &\overset{\eqref{eq:lemma3}}{\leq} \frac{\mu^2 L^2}{2} (\hat{n} + 4)^3 + 2\E_{\bar{\mathcal{U}}, \X}\left[\norm{\nabla f_\mu(\w^{(T)})}^2\right] \nonumber\\
&\overset{\eqref{b2}}{\leq} 16(\hat{n}+4)L\frac{f_\mu(\w^{(0)})- f_\mu^\star}{T+1} + \frac{\mu^2 L^2}{2} (\hat{n} + 4)^2\left(\hat{n} + \frac{11}{2}\right) \label{b3}
\end{align}
Now we lower-bound the expected number of iteration. In order to get $\epsilon$-accurate solution $\E_{\bar{\mathcal{U}}, \X}\left[\norm{\nabla f(\w^{(T)})}^2\right] \leq \epsilon^2$, we need to choose $\mu = \Omega\left(\frac{\epsilon}{\hat{n}^{\sfrac{3}{2}}L}\right)  \cdots \refstepcounter{equation}(\theequation)\label{b4}$ so that the second term in the right hand side of \eqref{b3} vanishes wrt. $\epsilon^2$.
\begin{align*}
16(\hat{n}+4)L\frac{f_\mu(\w^{(0)})- f_\mu^\star}{T+1} + \bigO(\mu^2 L^2 \hat{n}^3) &\overset{\eqref{b4}}{=} 16(\hat{n}+4)L\frac{f_\mu(\w^{(0)})- f_\mu^\star}{T+1} + \bigO(\epsilon^2)\\ &\overset{!}{=} \bigO(\epsilon^2) \\
T &= \bigO\left(\frac{\hat{n}L}{\epsilon^2}\right)
\end{align*}

\end{proof}

\subsection{Miscellaneous}\label{misc}
\begin{lemma}\label{lemma0}
For any $\ab, \bb \in \mathbb{R}^{n}$, we have
\begin{align}
    \norm{\ab}^2 &\leq 2\norm{\ab - \bb}^2 + 2\norm{\bb}^2 \label{eq:lemma0}
\end{align}
\end{lemma}

\begin{proof}
For any $\x, \y \in \mathbb{R}^{n}$, it holds
\begin{align*}
\norm{\x + \y}^2 + \norm{\x - \y}^2
&= \norm{\x}^2 + 2\langle\x, \y \rangle + \norm{\y}^2 + \norm{\x}^2 - 2\langle\x, \y \rangle + \norm{\y}^2\\
&= 2\norm{\x}^2 + 2\norm{\y}^2 .
\end{align*}
Dropping either $\norm{\x + \y}^2$ or $\norm{\x - \y}^2$ on the left hand side, we get
\begin{align}
\norm{\x \pm \y}^2 &\leq 2\norm{\x}^2 + 2\norm{\y}^2 \label{eq:misc}
\end{align}
Substitute $\x \leftarrow \ab - \bb$ and $\y \leftarrow \bb$ in $\norm{\x + \y}^2 \leq 2\norm{\x}^2 + 2\norm{\y}^2$. Then we get
\begin{align*}
\norm{\ab}^2 &\leq 2\norm{\ab - \bb}^2 + 2\norm{\bb}^2 .
\end{align*}
\end{proof}

\begin{lemma}\label{misc1}
Let be $t>0$, $p\geq 2$, and $\tau \in (0, 1)$. Then we have
\begin{align}
t^p e^{-\frac{\tau}{2}t^2} \leq \left(\frac{p}{\tau e}\right)^\frac{p}{2}. \label{eq:misc1}
\end{align}
\end{lemma}
\begin{proof}
Denote $\psi(t):= t^p e^{-\frac{\tau}{2}t^2}$ for some fixed $\tau\in(0,1)$. Find the point $t$ s.t. $\psi^{'}(t) = 0$.
\begin{align*}
\psi'(t) = pt^{p-1} e^{-\frac{\tau}{2}t^2} + t^p\left(-\tau t  e^{-\frac{\tau}{2}t^2}\right) &\overset{!}{=} 0\\
t&=\sqrt{\sfrac{p}{\tau}} & \text{ since }t>0, \tau\in(0,1)\\
\psi(\sqrt{\sfrac{p}{\tau}})&= \left(\sfrac{p}{\tau}\right)^\frac{p}{2} e^{-\sfrac{p}{2}}\\
&= \left(\frac{p}{\tau e}\right)^\frac{p}{2}
\end{align*}
Now we conduct the second derivative test.
\begin{align*}
\psi''(t) &= \left(\tau^2 t^2 e^{-\frac{\tau}{2} t^2} - \tau e^{-\frac{\tau}{2} t^2}\right) t^p + (p - 1) p e^{-\frac{\tau}{2} t^2} t^{p - 2} - 2 \tau p e^{-\frac{\tau}{2} t^2} t^p\\
&= e^{-\frac{\tau}{2} t^2} \cdot t^{p-2} \left(\tau^2 t^4 -2\tau p t^2 -\tau t^2 + p^2 -p\right)
\end{align*}
\begin{align*}
\psi''(\sqrt{\sfrac{p}{\tau}}) &= e^{-\frac{\bcancel{\tau}}{2}\frac{p}{\bcancel{\tau}}} \cdot \sqrt{\frac{p}{\tau}}^{p-2} \left(\bcancel{\tau^2} \left(\frac{p}{\bcancel{\tau}}\right)^2 -2\bcancel{\tau} p \frac{p}{\bcancel{\tau}} -\bcancel{\tau} \frac{p}{\bcancel{\tau}} + p^2 -p \right)\\
&= \underset{> 0}{\underbrace{\vphantom{\int}e^{-\frac{p}{2}}}} \underset{> 0}{\underbrace{\vphantom{\int}\left(\frac{p}{\tau}\right)^{\frac{p-2}{2}}}} \underset{< 0}{\left(\underbrace{\vphantom{\int}\bcancel{p^2} - \bcancel{2p^2} -p + \bcancel{p^2} -p}\right)} < 0 & \text{ since } p\geq 2
\end{align*}
Hence, we conclude that we have found a local maximum at $t = \sqrt{\sfrac{p}{\tau}}$, therefore $t^p e^{-\frac{\tau}{2}t^2} \leq \left(\frac{p}{\tau e}\right)^\frac{p}{2}$.
\end{proof}

\begin{lemma}\label{misc2}
Let be $t>0$, $p\geq 2$, $\tau \in (0, 1)$, and $n > 0$. Then we have
\begin{align}
\left(\frac{p}{\tau e}\right)^{\frac{p}{2}} (1-\tau)^{-\frac{n}{2}} \leq \left(p+n\right)^{\frac{p}{2}}\label{eq:misc2}
\end{align}
\end{lemma}
\begin{proof}
Denote $\phi(\tau):= \left(\frac{p}{\tau e}\right)^{\frac{p}{2}} (1-\tau)^{-\frac{n}{2}}$ for some fixed $\tau\in(0,1)$. Find the point $\tau$ s.t. $\phi'(\tau) = 0$.
\begin{align*}
\phi'(\tau)=\frac{ e^{-\frac{p}{2}} (1 - \tau)^{-\frac{n}{2} - 1} (\frac{p}{\tau})^{\frac{p}{2}} (n \tau + p (\tau - 1))}{2 \tau} &\overset{!}{=} 0\\
\tau&=\frac{p}{n+p} & \text{ since }n+p \neq 0, np \neq 0\\
\end{align*}
Let us check the sign of the second derivative of $\phi(\frac{p}{n+p})$.
\begin{align*}
\phi''(\tau)&=\frac{1}{4(\tau-1)^2\tau^2} e^{-\frac{p}{2}}\left(\frac{p}{\tau}\right)^{\frac{p}{2}} (1-\tau)^{-\frac{n}{2}} \left(\tau^2((p+ n)^2 + 2(p + n))\right. \\
&\hspace{20em}\left.- 2p \tau(p  + n) - 4p\tau + 2p\right)\\
\phi''(\frac{p}{n+p})&= \underset{>0}{\underbrace{\vphantom{\int}\frac{(n+p)^4}{4n^2p^2}}} ~ \underset{>0}{\underbrace{\vphantom{\int}e^{-\frac{p}{2}}}} ~\underset{>0}{\underbrace{\vphantom{\int}(n+p)^{\frac{p}{2}}}} ~\underset{>0}{\underbrace{\vphantom{\int}\left(\frac{n+p}{n}\right)^{\frac{n}{2}}}} ~\underset{<0}{\left(\underbrace{\vphantom{\int} -p^2 \left( 1+\frac{2}{p+n}\right) +2p}\right)} < 0
\end{align*}
since $p \geq 2, n > 0$. Therefore, $\phi(\tau)$ takes a local maximum at $\tau = \frac{p}{n+p}$. Then we obtain
\begin{align*}
\phi(\frac{p}{n+p})&= e^{-\frac{p}{2}} \left(p+n\right)^{\frac{p}{2}} \left(\frac{n+p-p}{n+p}\right)^{-\frac{n}{2}} \leq \left(p+n\right)^{\frac{p}{2}} .
\end{align*}
The last inequality follows because
\begin{align*}
e^{-\frac{p}{2}}\left(\frac{n}{n+p}\right)^{-\frac{n}{2}} &\leq 1 .
\end{align*}
\end{proof}

\begin{comment}
\begin{lemma}\label{misc3}
\begin{align}
\nabla f(\w) = \E_{\ug}\left[ \langle \nabla f(\w),\ug \rangle \ug  \right] \label{eq:misc3}
\end{align}
\end{lemma}
\begin{proof}
Let us denote the gradients $\nabla f(\w)$ wrt. $\w$ as a column vector of derivatives of each component in $\w$.
\begin{align*}
\nabla f(\w) = \left[\frac{\partial f}{\partial w_1}, \frac{\partial f}{\partial w_2}, \cdots \frac{\partial f}{\partial w_n}\right]^\top
\end{align*}
By definition of the scalar product, we have
\begin{align}
\langle \nabla f(\w),\ug \rangle = \sum_{j=1}^{n}\frac{\partial f}{\partial w_j} u_j \label{eq:f1}
\end{align}
Then we get
\begin{align}
\E_{\ug}\left[ \langle \nabla f(\w),\ug \rangle \ug  \right] &\overset{\eqref{eq:f1}}{=} \E_{\ug}\left[ \left(\sum_{j=1}^{n}\frac{\partial f}{\partial w_j} u_j\right) \ug\right] \nonumber\\
&= \sum_{j=1}^{n}\E_{\ug}\left[ \left(\frac{\partial f}{\partial w_j} u_j\right) \ug\right]\label{eq:f2}\\
&= \sum_{j=1}^{n}\frac{\partial f}{\partial w_j}\E_{\ug}\left[  u_j \cdot\ug\right] \nonumber\\
&=\sum_{j=1}^{n}\frac{\partial f}{\partial w_j}
\left[ \begin{array}{c}
\E \left[u_j \cdot u_1\right] \\
\E \left[u_j \cdot u_2\right] \\
\vdots \\
\E \left[u_j \cdot u_j\right]\\
\vdots \\
\E \left[u_j \cdot u_n\right] \\
\end{array}\right] \nonumber\\
&=\sum_{j=1}^{n}\frac{\partial f}{\partial w_j}
\left[ \begin{array}{c}
\E \left[u_j\right] \cdot \E \left[u_1\right] \\
\E \left[u_j\right] \cdot \E \left[u_2\right] \\
\vdots \\
\E \left[u_j^2\right]\\
\vdots \\
\E \left[u_j\right] \cdot \E \left[u_n\right] \\
\end{array}\right] \label{eq:f3}
\end{align}
We used the linearity of expectation in \eqref{eq:f2}. The last equality \eqref{eq:f3} follows because each component $u$ is independent. Since $u_j$ was drawn from $\N(0, 1)$, we know $\E[u_j] = 0$, and $\E[(u_j - 0)^2] = 1$. Then we obtain
\begin{align}
\E_{\ug}\left[ \langle \nabla f(\w),\ug \rangle \ug  \right] \overset{\eqref{eq:f3}}{=} \sum_{j=1}^{n}\frac{\partial f}{\partial w_j}
\left[ \begin{array}{c}
0 \\
0 \\
\vdots \\
1\\
\vdots \\
0 \\
\end{array}\right]
= \left[ \begin{array}{c}
\frac{\partial f}{\partial w_1} \\
\frac{\partial f}{\partial w_2} \\
\vdots \\
\frac{\partial f}{\partial w_j}\\
\vdots \\
\frac{\partial f}{\partial w_n} \\
\end{array}\right]
= \nabla f(\w)
\end{align}

\end{proof}
\end{comment}

\begin{lemma}\label{misc3}
\begin{align}
\nabla f(\w) = \E_{\ug}\left[ \langle \nabla f(\w),\ug \rangle \ug  \right] \label{eq:misc3}
\end{align}
\end{lemma}
\begin{proof}
Let us denote the gradients $\nabla f(\w)$ wrt. $\w$ as a column vector of derivatives of each component in $\w$.
\begin{align*}
\nabla f(\w) = \left[\frac{\partial f}{\partial w_1}, \frac{\partial f}{\partial w_2}, \cdots \frac{\partial f}{\partial w_n}\right]^\top
\end{align*}
By definition of the scalar product, we have
\begin{align}
\langle \nabla f(\w),\ug \rangle = \sum_{j=1}^{n}\frac{\partial f}{\partial w_j} u_j \label{eq:g1}
\end{align}
Then we get
\begin{align}
\E_{\ug}\left[ \langle \nabla f(\w),\ug \rangle \ug  \right] &\overset{\eqref{eq:g1}}{=} \E_{\ug}\left[ \left(\sum_{j=1}^{n}\frac{\partial f}{\partial w_j} u_j\right) \ug\right] \nonumber\\
&= \sum_{j=1}^{n}\E_{\ug}\left[ \left(\frac{\partial f}{\partial w_j} u_j\right) \ug\right]\label{eq:g2}\\
&= \sum_{j=1}^{n}\frac{\partial f}{\partial w_j}\E_{\ug}\left[  u_j \cdot\ug\right] \nonumber\\
&=\sum_{j=1}^{n}\frac{\partial f}{\partial w_j}
\left[ \begin{array}{c}
\E \left[u_j \cdot u_1\right] \\
\E \left[u_j \cdot u_2\right] \\
\vdots \\
\E \left[u_j \cdot u_j\right]\\
\vdots \\
\E \left[u_j \cdot u_n\right] \\
\end{array}\right] \nonumber\\
&=\sum_{j=1}^{n}\frac{\partial f}{\partial w_j}
\left[ \begin{array}{c}
\E \left[u_j\right] \cdot \E \left[u_1\right] \\
\E \left[u_j\right] \cdot \E \left[u_2\right] \\
\vdots \\
\E \left[u_j^2\right]\\
\vdots \\
\E \left[u_j\right] \cdot \E \left[u_n\right] \\
\end{array}\right] \label{eq:g3}
\end{align}
We used the linearity of expectation in \eqref{eq:g2}. The last equality \eqref{eq:g3} follows because each component $u$ is independent. Since $u_j$ was drawn from $\N(0, 1)$, we know $\E[u_j] = 0$, and $\E[(u_j - 0)^2] = 1$. Then we obtain
\begin{align}
\E_{\ug}\left[ \langle \nabla f(\w),\ug \rangle \ug \right] \overset{\eqref{eq:g3}}{=} \sum_{j=1}^{n}\frac{\partial f}{\partial w_j}
\left[ \begin{array}{c}
0 \\
0 \\
\vdots \\
1\\
\vdots \\
0 \\
\end{array}\right]
= \left[ \begin{array}{c}
\frac{\partial f}{\partial w_1} \\
\frac{\partial f}{\partial w_2} \\
\vdots \\
\frac{\partial f}{\partial w_j}\\
\vdots \\
\frac{\partial f}{\partial w_n} \\
\end{array}\right]
= \nabla f(\w)
\end{align}

\end{proof}

\subsection{Empirical Sparsity}\label{sparsity}

Figures \ref{fig:sparsity-cifar} and \ref{fig:sparsity-mnist} illustrate our observation of empirical gradient sparsity across the entire learning process on both MNIST and CIFAR classification tasks. The histograms on the right side show that the majority of gradient coordinates have value zero throughout the learning process, while the values of the learned weight vector are centered around non-zero values, except obviously for pruning approaches.

\begin{figure}
    \centering
\begin{tabular}{ccc}

     \rotatebox[origin=t]{90}{dense}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_none-last-none_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_none-last-none_true-grad.pdf}}\\%&\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_none-last-none_approx-grad.pdf}\\
     \rotatebox[origin=t]{90}{prune-L1}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_prune-last-L1_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_prune-last-L1_true-grad.pdf}}\\%&\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_prune-last-L1_approx-grad.pdf}\\
     \rotatebox[origin=t]{90}{prune-random}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_prune-last-random_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_prune-last-random_true-grad.pdf}}\\%&\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_prune-last-random_approx-grad.pdf}\\
     \rotatebox[origin=t]{90}{freeze-L1}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_freeze-last-L1_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_freeze-last-L1_true-grad.pdf}}\\%&\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_freeze-last-L1_approx-grad.pdf}\\
     \rotatebox[origin=t]{90}{freeze-random}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_freeze-last-random_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/CIFAR_404_freeze-last-random_true-grad.pdf}}
\end{tabular}
    \caption{Empirical gradient sparsity and values of learned weight vector for CIFAR-10.}
    \label{fig:sparsity-cifar}
\end{figure}

\begin{figure}
    \centering
\begin{tabular}{ccc}

     \rotatebox[origin=c]{90}{dense}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_none-last-none_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_none-last-none_true-grad.pdf}}\\
     \rotatebox[origin=t]{90}{prune-L1}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_prune-last-L1_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_prune-last-L1_true-grad.pdf}}\\
     \rotatebox[origin=t]{90}{prune-random}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_prune-last-random_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_prune-last-random_true-grad.pdf}}\\
     \rotatebox[origin=t]{90}{freeze-L1}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_freeze-last-L1_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_freeze-last-L1_true-grad.pdf}}\\
     \rotatebox[origin=t]{90}{freeze-random}& \makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_freeze-last-random_weights.pdf}}&\makecell{\includegraphics[trim={3em 0 0 0},clip,width=0.45\textwidth]{img/MNIST_31_freeze-last-random_true-grad.pdf}}
\end{tabular}
    \caption{Empirical gradient sparsity and values of learned weight vector for MNIST.}
    \label{fig:sparsity-mnist}
\end{figure}

\end{document}

config: arxiv