Laplacian Smoothing Gradient Descent
This incremental improvement addresses optimization challenges for machine learning practitioners by enhancing convergence and generalization in gradient-based methods.
The authors tackled the problem of high variance and limited step sizes in gradient descent and stochastic gradient descent by proposing a simple modification that multiplies the gradient by the inverse of a low-condition-number matrix derived from a discrete Laplacian, resulting in reduced variance, larger step sizes, and improved generalization accuracy across various machine learning tasks like logistic regression and deep neural networks.
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 logistic regression to deep neural nets, the proposed surrogates can dramatically reduce the variance, allow to take a larger step size, and improve the generalization accuracy. The methods only involve multiplying the usual (stochastic) gradient by the inverse of a positive definitive matrix (which can be computed efficiently by FFT) with a low condition number coming from a one-dimensional discrete Laplacian or its high order generalizations. It also preserves the mean and increases the smallest component and decreases the largest component. The theory of Hamilton-Jacobi partial differential equations demonstrates that the implicit version of the 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". Moreover, 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. The code is available at: \url{https://github.com/BaoWangMath/LaplacianSmoothing-GradientDescent}