We propose a class of very simple modifications of gradient descent and stochastic gradient descent. We show that when applied to a large variety of machine learning problems, ranging from softmax regression to deep neural nets, the proposed surrogates can dramatically reduce the variance and improve the generalization accuracy. The methods only involve multiplying the usual (stochastic) gradient by the inverse of a positive definitive matrix coming from the discrete Laplacian or its high order generalizations. The theory of Hamilton-Jacobi partial differential equations demonstrates that the implicit version of new algorithm is almost the same as doing gradient descent on a new function which (i) has the same global minima as the original function and (ii) is "more convex". We show that optimization algorithms with these surrogates converge uniformly in the discrete Sobolev H p σ sense and reduce the optimality gap for convex optimization problems. We implement our algorithm into both PyTorch and Tensorflow platforms which only involves changing of a few lines of code. The code will be available on Github.
The paper considers SGD with a scaled norm; in the non-stochastic case (first equation in section 2.1), it is gradient descent in a fixed non-Euclidean norm, but it is the stochastic case that is most interesting. The paper connects this, somewhat, to a Hamilton-Jacobi equation, but then relaxes the implicit step to an explicit step.
There is solid theory (Prop 2, 3 and 4) for convergence, which makes sense since this is the same as usual SGD but in a different Hilbert space. Since the inner product is stationary, it's just a fixed Hilbert space, so any convergence proofs that work for arbitrary Hilbert space immediately give the result.
The computational experiments are impressive, and demonstrate a lot of competence with modern neural nets. Some results are hard to interpret (Figs 9, 10) though.
As for why use the Laplacian, Prop 8 (combined with Prop 6) gives some idea: that we lower the variance, without cheating (ie., we could trivially lower the variance by just multiplying by a small number, but because the operator preserves the sum of the components, it is not "cheating").  That is helpful, though it doesn't give a complete picture yet.  The explanation about the link to the "more convex" function I find completely inaccurate and misleading (see technical comments for why).
The writing is mainly fine, though some sentences are written poorly and would benefit from a revision, e.g., 2nd paragraph, "But none of them is suitable to train deep neural nets (DNNs)." is quite awkward [also, in this sentence, please explain *why* they are not suitable!]
The paper circumvents the page limit by using a smaller font (starting on page 3). This might seem like a minor issue, but it is violating the page limit, and not fair to other papers (unless I have misunderstood; the meta-reviewers can probably comment about this).  I do not think it would be unfair to reject the paper on these grounds. It leaves a bad taste in my mouth after reading the paper.
Technical comments:
- page 1, this is called a "tri-diagonal" linear system, but it is not, it is circulant due to the upper-right and lower-left entries (the authors are well-aware of this, but the reader maybe confused; especially since if it were tri-diagonal, it would be inverted via the Thomas algorithm not the FFT).
- Section 2: my first impression on reading this is that you've re-discovered the proximal point envelope and the Moreau envelope (and, looking at the proof of Prop. 1, the authors are aware of this connection).  In this context, it's not clear why A_sigma is helpful, as opposed to any positive definite matrix.
- The actual statement of Proposition 1 is unclear. What does "the ... update ... permits .." mean? i.e., "permits" is a weird, vague choice of words. What are you actually proving?
- Section 2.1 moves from the proximal point method (in a scaled norm) to the gradient descent method (in a scaled norm). Clearly, these two methods are different, and just as in ODE schemes, the implicit version is unconditionally stable while the explicit one isn't. So motivating your method by "smoothing" or "adding convexity" is really misleading. You could define equation (2) and the u(w,t) equation by replacing A_sigma with the identity, and as long as tau > 0, this also "convexifies", but then if you go from implicit to explicit, you get regular GD, so you haven't really done anything.  So, I do not buy this connection that your method "convexifies" the function.
- Using the FFT to invert seems slow (the theoretical flop-count is good, but it's still super-linear, and requires global data movement, so not good for a distributed implementation).  If you really did define A to be tri-diagonal, then you could invert naively in a linear time algorithm with local data movement. Why not use a tri-diagonal A? It might not satisfy prop 8 exactly, but it'd be close, and a lot faster in practice.  From a "finite-difference" point-of-view, I don't see an inherent argument about why you want circular boundary conditions.
- Remark 1 seems out-of-place. Why is that included?
- Section 3.2, and Fig. 5.  It's not clear that the improved generalization results are due to broader local minima, or if it's because the methods converged faster on the training data (since they were limited to 200 epochs). Showing the training error, as a function of epoch, would help clarify. Similar comment for other experiments too.
- Section 4 was impressive in the implementations. Nice work.
- The acknowledgments used the boiler-plate latex template text.
** summary **
Quality: Good
Clarity: OK
Originality: mixed
Significance: maybe high?