Laplacian Smoothing Gradient Descent

Abstract

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_{\sigma }^p$ sense and reduce the optimality gap for convex optimization problems. The code is available at: \url{https://github.com/BaoWangMath/LaplacianSmoothing-GradientDescent}

28 pages, 15 figures

References in corpus (7)

• Deep Learning in Neural Networks: An Overview
• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Towards Principled Methods for Training Generative Adversarial Networks
• On the Relation Between the Sharpest Directions of DNN Loss and the SGD Step Length

Cited by in corpus (14)

• Stochastic Training of Residual Networks: a Differential Equation Viewpoint
• DP-LSSGD: A Stochastic Optimization Method to Lift the Utility in Privacy-Preserving ERM
• Particle-based Energetic Variational Inference
• Differentially Private Federated Learning with Laplacian Smoothing
• Mathematical Analysis of Adversarial Attacks
• Batch Normalization Preconditioning for Neural Network Training
• Learning Green's Functions of Linear Reaction-Diffusion Equations with Application to Fast Numerical Solver
• Modes of Homogeneous Gradient Flows
• A Study on Graph-Structured Recurrent Neural Networks and Sparsification with Application to Epidemic Forecasting
• Laplacian Smoothing Stochastic Gradient Markov Chain Monte Carlo
• Channel-Directed Gradients for Optimization of Convolutional Neural Networks
• Graph Interpolating Activation Improves Both Natural and Robust Accuracies in Data-Efficient Deep Learning
• An efficient method for computing stationary states of phase field crystal models
• A Deterministic Gradient-Based Approach to Avoid Saddle Points