A Deterministic Gradient-Based Approach to Avoid Saddle Points

Lisa Maria Kreusser; Stanley J. Osher; Bao Wang

doi:10.1017/S0956792522000316

A Deterministic Gradient-Based Approach to Avoid Saddle Points

Lisa Maria Kreusser, Stanley J. Osher, Bao Wang

Research output: Contribution to journal › Article › peer-review

63 Downloads (Pure)

Abstract

Loss functions with a large number of saddle points are one of the major obstacles for training modern machine learning (ML) models efficiently. First-order methods such as gradient descent (GD) are usually the methods of choice for training ML models. However, these methods converge to saddle points for certain choices of initial guesses. In this paper, we propose a modification of the recently proposed Laplacian smoothing gradient descent (LSGD) [Osher et al., arXiv:1806.06317], called modified LSGD (mLSGD), and demonstrate its potential to avoid saddle points without sacrificing the convergence rate. Our analysis is based on the attraction region, formed by all starting points for which the considered numerical scheme converges to a saddle point. We investigate the attraction region’s dimension both analytically and numerically. For a canonical class of quadratic functions, we show that the dimension of the attraction region for mLSGD is ⌊(n − 1)/2⌋, and hence it is significantly smaller than that of GD whose dimension is n − 1.

Original language	English
Pages (from-to)	738-757
Number of pages	20
Journal	European Journal of Applied Mathematics
Volume	34
Issue number	4
Early online date	9 Nov 2022
DOIs	https://doi.org/10.1017/S0956792522000316
Publication status	Published - 31 Aug 2023

Bibliographical note

This material is based on research sponsored by the National Science Foundation under grant numbers DMS-1924935, DMS-1952339, DMS-1554564 (STROBE), DMS-2152762 and DMS-2208361, the Air Force Research Laboratory under grant numbers FA9550-18-0167 and MURI FA9550-18-1-0502, the Office of Naval Research under the grant number N00014-18-1-2527 and the Department of Energy under the grant number DE-SC0021142 and DE-SC0002722. LMK acknowledges support from the German National Academic Foundation (Studienstiftung des Deutschen Volkes), the European Union Horizon 2020 research and innovation programmes under the Marie Skłodowska-Curie grant agreement No. 777826 (NoMADS) and No. 691070 (CHiPS), the Cantab Capital Institute for the Mathematics of Information and Magdalene College, Cambridge (Nevile Research Fellowship). SJO was partially funded by the Office of Naval Research under the grant numbers N00014-18-20-1-2093 and N00014-20-1-2787.

Funding

Acknowledgements. This material is based on research sponsored by the National Science Foundation under grant numbers DMS-1924935, DMS-1952339, DMS-1554564 (STROBE), DMS-2152762 and DMS-2208361, the Air Force Research Laboratory under grant numbers FA9550-18-0167 and MURI FA9550-18-1-0502, the Office of Naval Research under the grant number N00014-18-1-2527 and the Department of Energy under the grant number DE-SC0021142 and DE-SC0002722. LMK acknowledges support from the German National Academic Foundation (Studienstiftung des Deutschen Volkes), the European Union Horizon 2020 research and innovation programmes under the Marie Skłodowska-Curie grant agreement No. 777826 (NoMADS) and No. 691070 (CHiPS), the Cantab Capital Institute for the Mathematics of Information and Magdalene College, Cambridge (Nevile Research Fellowship). SJO was partially funded by the Office of Naval Research under the grant numbers N00014-18-20-1-2093 and N00014-20-1-2787.

Funders	Funder number
CHiPS
Cantab Capital Institute for the Mathematics of Information and Magdalene College, Cambridge	N00014-18-20-1-2093, N00014-20-1-2787
National Science Foundation	DMS-2208361, DMS-1952339, DMS-1924935, DMS-2152762, DMS-1554564
Office of Naval Research	N00014-18-1-2527
U.S. Department of Energy	DE-SC0002722, DE-SC0021142
Air Force Research Laboratory	FA9550-18-0167
H2020 Marie Skłodowska-Curie Actions	691070, 777826
Multidisciplinary University Research Initiative	FA9550-18-1-0502
Studienstiftung des Deutschen Volkes
Horizon 2020

Keywords

cs.LG
cs.NA
math.DS
math.NA
stat.ML
attraction region
saddle points
gradient-based methods
Laplacian smoothing
Deterministic algorithm

ASJC Scopus subject areas

Applied Mathematics

Access to Document

10.1017/S0956792522000316

1901.06827v2.PDFAccepted author manuscript, 757 KBLicence: CC BY-NC-ND

Cite this

@article{87aee974a7b0424aaace33e855626c20,

title = "A Deterministic Gradient-Based Approach to Avoid Saddle Points",

abstract = "Loss functions with a large number of saddle points are one of the major obstacles for training modern machine learning (ML) models efficiently. First-order methods such as gradient descent (GD) are usually the methods of choice for training ML models. However, these methods converge to saddle points for certain choices of initial guesses. In this paper, we propose a modification of the recently proposed Laplacian smoothing gradient descent (LSGD) [Osher et al., arXiv:1806.06317], called modified LSGD (mLSGD), and demonstrate its potential to avoid saddle points without sacrificing the convergence rate. Our analysis is based on the attraction region, formed by all starting points for which the considered numerical scheme converges to a saddle point. We investigate the attraction region{\textquoteright}s dimension both analytically and numerically. For a canonical class of quadratic functions, we show that the dimension of the attraction region for mLSGD is ⌊(n − 1)/2⌋, and hence it is significantly smaller than that of GD whose dimension is n − 1.",

keywords = "cs.LG, cs.NA, math.DS, math.NA, stat.ML, attraction region, saddle points, gradient-based methods, Laplacian smoothing, Deterministic algorithm",

author = "Kreusser, {Lisa Maria} and Osher, {Stanley J.} and Bao Wang",

note = "This material is based on research sponsored by the National Science Foundation under grant numbers DMS-1924935, DMS-1952339, DMS-1554564 (STROBE), DMS-2152762 and DMS-2208361, the Air Force Research Laboratory under grant numbers FA9550-18-0167 and MURI FA9550-18-1-0502, the Office of Naval Research under the grant number N00014-18-1-2527 and the Department of Energy under the grant number DE-SC0021142 and DE-SC0002722. LMK acknowledges support from the German National Academic Foundation (Studienstiftung des Deutschen Volkes), the European Union Horizon 2020 research and innovation programmes under the Marie Sk{\l}odowska-Curie grant agreement No. 777826 (NoMADS) and No. 691070 (CHiPS), the Cantab Capital Institute for the Mathematics of Information and Magdalene College, Cambridge (Nevile Research Fellowship). SJO was partially funded by the Office of Naval Research under the grant numbers N00014-18-20-1-2093 and N00014-20-1-2787. ",

year = "2023",

month = aug,

day = "31",

doi = "10.1017/S0956792522000316",

language = "English",

volume = "34",

pages = "738--757",

journal = "European Journal of Applied Mathematics",

issn = "0956-7925",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - A Deterministic Gradient-Based Approach to Avoid Saddle Points

AU - Kreusser, Lisa Maria

AU - Osher, Stanley J.

AU - Wang, Bao

N1 - This material is based on research sponsored by the National Science Foundation under grant numbers DMS-1924935, DMS-1952339, DMS-1554564 (STROBE), DMS-2152762 and DMS-2208361, the Air Force Research Laboratory under grant numbers FA9550-18-0167 and MURI FA9550-18-1-0502, the Office of Naval Research under the grant number N00014-18-1-2527 and the Department of Energy under the grant number DE-SC0021142 and DE-SC0002722. LMK acknowledges support from the German National Academic Foundation (Studienstiftung des Deutschen Volkes), the European Union Horizon 2020 research and innovation programmes under the Marie Skłodowska-Curie grant agreement No. 777826 (NoMADS) and No. 691070 (CHiPS), the Cantab Capital Institute for the Mathematics of Information and Magdalene College, Cambridge (Nevile Research Fellowship). SJO was partially funded by the Office of Naval Research under the grant numbers N00014-18-20-1-2093 and N00014-20-1-2787.

PY - 2023/8/31

Y1 - 2023/8/31

N2 - Loss functions with a large number of saddle points are one of the major obstacles for training modern machine learning (ML) models efficiently. First-order methods such as gradient descent (GD) are usually the methods of choice for training ML models. However, these methods converge to saddle points for certain choices of initial guesses. In this paper, we propose a modification of the recently proposed Laplacian smoothing gradient descent (LSGD) [Osher et al., arXiv:1806.06317], called modified LSGD (mLSGD), and demonstrate its potential to avoid saddle points without sacrificing the convergence rate. Our analysis is based on the attraction region, formed by all starting points for which the considered numerical scheme converges to a saddle point. We investigate the attraction region’s dimension both analytically and numerically. For a canonical class of quadratic functions, we show that the dimension of the attraction region for mLSGD is ⌊(n − 1)/2⌋, and hence it is significantly smaller than that of GD whose dimension is n − 1.

AB - Loss functions with a large number of saddle points are one of the major obstacles for training modern machine learning (ML) models efficiently. First-order methods such as gradient descent (GD) are usually the methods of choice for training ML models. However, these methods converge to saddle points for certain choices of initial guesses. In this paper, we propose a modification of the recently proposed Laplacian smoothing gradient descent (LSGD) [Osher et al., arXiv:1806.06317], called modified LSGD (mLSGD), and demonstrate its potential to avoid saddle points without sacrificing the convergence rate. Our analysis is based on the attraction region, formed by all starting points for which the considered numerical scheme converges to a saddle point. We investigate the attraction region’s dimension both analytically and numerically. For a canonical class of quadratic functions, we show that the dimension of the attraction region for mLSGD is ⌊(n − 1)/2⌋, and hence it is significantly smaller than that of GD whose dimension is n − 1.

KW - cs.LG

KW - cs.NA

KW - math.DS

KW - math.NA

KW - stat.ML

KW - attraction region

KW - saddle points

KW - gradient-based methods

KW - Laplacian smoothing

KW - Deterministic algorithm

UR - http://www.scopus.com/inward/record.url?scp=85174142192&partnerID=8YFLogxK

U2 - 10.1017/S0956792522000316

DO - 10.1017/S0956792522000316

M3 - Article

SN - 0956-7925

VL - 34

SP - 738

EP - 757

JO - European Journal of Applied Mathematics

JF - European Journal of Applied Mathematics

IS - 4

ER -

A Deterministic Gradient-Based Approach to Avoid Saddle Points

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this