Convergence of Gradient Descent on Separable Data
  We provide a detailed study on the implicit bias of gradient descent when
optimizing loss functions with strictly monotone tails, such as the logistic
loss, over separable datasets. We look at two basic questions: (a) what are the
conditions on the tail of the loss function under which gradient descent
converges in the direction of the $L_2$ maximum-margin separator? (b) how does
the rate of margin convergence depend on the tail of the loss function and the
choice of the step size? We show that for a large family of super-polynomial
tailed losses, gradient descent iterates on linear networks of any depth
converge in the direction of $L_2$ maximum-margin solution, while this does not
hold for losses with heavier tails. Within this family, for simple linear
models we show that the optimal rates with fixed step size is indeed obtained
for the commonly used exponentially tailed losses such as logistic loss.
However, with a fixed step size the optimal convergence rate is extremely slow
as $1/\log(t)$, as also proved in Soudry et al. (2018). For linear models with
exponential loss, we further prove that the convergence rate could be improved
to $\log (t) /\sqrt{t}$ by using aggressive step sizes that compensates for the
rapidly vanishing gradients. Numerical results suggest this method might be
useful for deep networks.
