Practise: Going Downhill on Purpose

The test from section 17.1 is the inner product $g\cdot d$. Compute it for each arrow: $$g\cdot (1,2)=3-4=-1,g\cdot (2,1)=6-2=4,$$ $$g\cdot (2,-1)=6+2=8,g\cdot (3,2)=9-4=5.$$ Only A scores below zero, so only A is a descent direction. The other three make an acute angle with the gradient and increase the loss to first order. The size of the score is not the step: A says the loss falls at rate 1 per unit of travel, and the step length is chosen separately. B, C and D are not downhill at this setting even though D is the longest arrow; length does not decide direction.

The partial derivatives are $\partial f/\partial x=2x$ and $\partial f/\partial y=8y$. At $(2,0.5)$ the gradient is $(4,4)$, and the starting loss is $2^2+4(0.5{)}^2=4+1=5$. The update gives $$(x_1,y_1)=(2,0.5)-0.1(4,4)=(1.6,0.1).$$ The new loss is $$f(1.6,0.1)=1.6^2+4(0.1{)}^2=2.56+0.04=\mathrm{2.6.}$$ The step lowered the loss by $5-2.6=2.4$. Check the direction test: the step is $-0.1g$, so $g\cdot (-0.1g)=-0.1\Vert g{\Vert }^2=-0.1(32)=-3.2<0$, which is the first-order prediction of the fall. The actual fall, 2.4, is smaller because the quadratic term is positive along this step: a step of $0.1$ costs $\frac{1}{2}(0.1{)}^2{g}^{\top }Hg=0.005(2\cdot 16+8\cdot 16)=0.8$, and $3.2-0.8=2.4$.

For $f(x)=3x^2$ the gradient is $6x$, so the update is $$x_{t+1}=x_t-0.1(6x_t)=(1-0.6)x_t=0.4x_t.$$ The factor is $1-\eta L$ with $L=6$. Starting at $x_0=1$: $$x_1=0.4,x_2=0.16,x_3=\mathrm{0.064.}$$ The run converges because $|0.4|<1$, which is the same as $0<\eta <2/L=1/3$. The loss after three steps is $3(0.064{)}^2=0.012288$, against $3$ at the start. The step $0.1$ is below $1/L=1/6\approx 0.167$, so the run is cautious: it removes 60 per cent of the distance per step rather than landing at the bottom, which a step of $1/L$ would do on this quadratic.

The gradient is $10x$, so one step gives $x_{t+1}=(1-10\eta )x_t$. The distance from the bottom is multiplied by the same factor at every step. It shrinks when $$|1-10\eta |<1,$$ which is $0<\eta <0.2$. At $\eta =0.2$ the multiplier is $1-2=-1$: the setting changes sign at every step and keeps the same distance, so the run bounces between two points forever. Above $0.2$ the multiplier is below $-1$ and the distance grows without bound. The value $0.2$ is $2/L=2/10$; it is the boundary of the window, not a converging step.

At $(1,3)$ the gradient is $(2,24)$, and $$\Vert g{\Vert }^2=2^2+24^2=4+576=580.$$ With $L=8$ and a step of $1/L=0.125$, the descent lemma of section 17.3 gives $$f\left(\theta -\frac{1}{L}g\right)\le f(\theta )-\frac{\Vert g{\Vert }^2}{2L}=37-\frac{580}{16}=37-36.25=\mathrm{0.75.}$$ So the guaranteed fall is $36.25$. Check it against the actual step. The new point is $(1,3)-0.125(2,24)=(0.75,0)$, whose loss is $0.5625$. The actual fall is $37-0.5625=36.4375$, which is $0.1875$ more than the floor. The floor is a promise about the worst case, so the actual fall may exceed it. Here the ratio of actual fall to floor is $36.4375/36.25\approx 1.005$.

Section 17.4 gives $$f({\theta }_t)-f({\theta }^{\ast })\le {\left(1-\frac{1}{\kappa }\right)}^t[f({\theta }_0)-f({\theta }^{\ast })]=50(0.96{)}^t.$$ Set the right side below 1 and take logarithms: $$50(0.96{)}^t<1⟺t>\frac{\ln (1/50)}{\ln (0.96)}=\frac{-3.9120}{-0.04082}=\mathrm{95.83.}$$ The smallest whole number above $95.83$ is 96. Check both sides of the boundary: at $t=95$ the gap is $50(0.96{)}^{95}=1.0345$, still above 1, and at $t=96$ it is $50(0.96{)}^{96}=0.9931$, below 1. The count is a bound, not a promise about a particular run: a quadratic can do better, and a general convex loss can do worse than the bound predicts.

The table gradient is $$\bar{g}=\frac{2+4+10+12}{4}=7.$$ The deviations are $-5,-3,3,5$, whose squares are $25,9,9,25$ and sum to $68$. The variance of one example's gradient is $${\sigma }^2=\frac{68}{4}=17.$$ The average of four independent draws has variance ${\sigma }^2/b=17/4=4.25$. Four times the examples buy a quarter of the noise, as section 17.5 says. The mean of the minibatch gradient is still 7, so the batch is unbiased; only its spread shrinks. A batch of one has variance 17, and a batch of 68 would bring the variance to $17/68=0.25$.

Test each schedule against the two conditions of section 17.6. A: $\sum 1/t$ is the harmonic series, which diverges; $\sum 1/t^2$ converges to ${\pi }^2/6\approx 1.645$. Both conditions hold. B: $\sum 1/t^2$ converges, so the total travel is finite, about $1.645$; a run started farther than that from the bottom can never arrive. The first condition fails. C: $\sum 1/\sqrt{t}$ diverges, so travel is unlimited, but $\sum 1/t$ also diverges, so the noise never averages away. The second condition fails. D: both sums diverge, because every term is the positive constant $0.1$ or $0.01$. The second condition fails, and the run settles at a noise floor. Only A passes both tests. Passing the tests says the schedule can work, not that it is the fastest; section 17.6 makes that limit explicit.