Laplacian Smoothing Gradient Descent

2018/06/17 by Stanley Osher, Osher, Stanley, Bao Wang +10 · 3 citations
Computer Science · Engineering · Physics and Astronomy · #65-06 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1806.06317

openalex publication_date 2018/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

Citations

• ADADELTA: An Adaptive Learning Rate Method
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• A Stochastic Approximation Method
• Deep Learning in Neural Networks: An Overview
• Convergence analysis of gradient descent stochastic algorithms
• Gradient-based learning applied to document recognition
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp\n Minima
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Learning Multiple Layers of Features from Tiny Images

Cited by

• A Study on Graph-Structured Recurrent Neural Networks and Sparsification with Application to Epidemic Forecasting
• DP-LSSGD: A Stochastic Optimization Method to Lift the Utility in Privacy-Preserving ERM
• An efficient method for computing stationary states of phase field crystal models

Related

• Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions
• A Deterministic Gradient-Based Approach to Avoid Saddle Points
• Improving SGD convergence by online linear regression of gradients in\n multiple statistically relevant directions
• Gradient Descent, Stochastic Optimization, and Other Tales
• Improved Performance of Stochastic Gradients with Gaussian Smoothing