  Learning rate schedule can significantly affect generalization performance in
modern neural networks, but the reasons for this are not yet understood.
Li-Wei-Ma (2019) recently proved this behavior can exist in a simplified
non-convex neural-network setting. In this note, we show that this phenomenon
can exist even for convex learning problems -- in particular, linear regression
in 2 dimensions.
  We give a toy convex problem where learning rate annealing (large initial
learning rate, followed by small learning rate) can lead gradient descent to
minima with provably better generalization than using a small learning rate
throughout. In our case, this occurs due to a combination of the mismatch
between the test and train loss landscapes, and early-stopping.
