THE IMPLICIT BIAS OF GRADIENT DESCENT ON SEPA- RABLE DATA
We show that gradient descent on an unregularized logistic regression problem, for almost all separable datasets, converges to the same direction as the max-margin solution. The result generalizes also to other monotone decreasing loss functions with an infimum at infinity, and we also discuss a multi-class generalizations to the cross entropy loss. Furthermore, we show this convergence is very slow, and only logarithmic in the convergence of the loss itself. This can help explain the benefit of continuing to optimize the logistic or cross-entropy loss even after the training error is zero and the training loss is extremely small, and, as we show, even if the validation loss increases. Our methodology can also aid in understanding implicit regularization in more complex models and with other optimization methods.
The paper offers a formal proof that gradient descent on the logistic
loss converges very slowly to the hard SVM solution in the case where
the data are linearly separable. This result should be viewed in the
context of recent attempts at trying to understand the generalization
ability of neural networks, which have turned to trying to understand
the implicit regularization bias that comes from the choice of
optimizer. Since we do not even understand the regularization bias of
optimizers for the simpler case of linear models, I consider the paper's
topic very interesting and timely.
The overall discussion of the paper is well written, but on a more
detailed level the paper gives an unpolished impression, and has many
technical issues. Although I suspect that most (or even all) of these
issues can be resolved, they interfere with checking the correctness of
the results. Unfortunately, in its current state I therefore do not
consider the paper ready for publication.
Technical Issues:
The statement of Lemma 5 has a trivial part and for the other part the
proof is incorrect: Let x_u = ||nabla L(w(u))||^2.
  - Then the statement sum_{u=0}^t x_u < infinity is trivial, because
    it follows directly from ||nabla L(w(u))||^2 < infinity for all u. I
    would expect the intended statement to be sum_{u=0}^infinity x_u <
    infinity, which actually follows from the proof of the lemma.
  - The proof of the claim that t*x_t -> 0 is incorrect: sum_{u=0}^t x_u
    < infinity does not in itself imply that t*x_t -> 0, as claimed. For
    instance, we might have x_t = 1/i^2 when t=2^i for i = 1,2,... and
    x_t = 0 for all other t.
Definition of tilde{w} in Theorem 4:
  - Why would tilde{w} be unique? In particular, if the support vectors
    do not span the space, because all data lie in the same
    lower-dimensional hyperplane, then this is not the case.
  - The KKT conditions do not rule out the case that \hat{w}^top x_n =
    1, but alpha_n = 0 (i.e. a support vector that touches the margin,
    but does not exert force against it). Such n are then included in
    cal{S}, but lead to problems in (2.7), because they would require
    tilde{w}^top x_n = infinity, which is not possible.
In the proof of Lemma 6, case 2. at the bottom of p.14:
  - After the first inequality, C_0^2 t^{-1.5 epsilon_+} should be 
    C_0^2 t^{-epsilon_+}
  - After the second inequality the part between brackets is missing an
    additional term C_0^2 t^{-\epsilon_+}.
  - In addition, the label (1) should be on the previous inequality and
    it should be mentioned that e^{-x} <= 1-x+x^2 is applied for x >= 0
    (otherwise it might be false).
In the proof of Lemma 6, case 2 in the middle of p.15:
  - In the line of inequality (1) there is a t^{-epsilon_-} missing. In
    the next line there is a factor t^{-epsilon_-} too much.
  - In addition, the inequality e^x >= 1 + x holds for all x, so no need
    to mention that x > 0.
In Lemma 1:
  - claim (3) should be lim_{t \to \infty} w(t)^\top x_n = infinity
  - In the proof: w(t)^top x_n > 0 only holds for large enough t.
Remarks:
p.4 The claim that "we can expect the population (or test)
misclassification error of w(t) to improve" because "the margin of w(t)
keeps improving" is worded a little too strongly, because it presumes
that the maximum margin solution will always have the best
generalization error.
In the proof sketch (p.3):
  - Why does the fact that the limit is dominated by gradients that are
    a linear combination of support vectors imply that w_infinity will
    also be a non-negative linear combination of support vectors?
  - "converges to some limit". Mention that you call this limit
    w_infinity
Minor Issues:
In (2.4): add "for all n".
p.10, footnote: Shouldn't "P_1 = X_s X_s^+" be something like "P_1 =
(X_s^top X_s)^+"?
A.9: ell should be ell'
The paper needs a round of copy editing. For instance:
  - top of p.4: "where tilde{w} A is the unique"
  - p.10: "the solution tilde{w} to TO eq. A.2"
  - p.10: "might BOT be unique"
  - p.10: "penrose-moorse pseudo inverse" -> "Moore-Penrose
    pseudoinverse"
  
In the bibliography, Kingma and Ba is cited twice, with different years.